akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstring>
using namespace std;

int main() {
	// your code goes here
	int n;
	cin>>n;
	int a[n+1],b[n+1],c[n+1];
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i]>>c[i];
	}
	int dp[n+1][3];
	memset(dp, 0, sizeof(dp));
	for(int i=1;i<=n;i++) {
		dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + a[i];
		dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + b[i];
		dp[i][2] = max(dp[i-1][1], dp[i-1][0]) + c[i];
	}
	int v = max(dp[n][0],dp[n][1]);
	int s = max(v,dp[n][2]);
	cout<<s;
	return 0;
}

Measured memory_bytes: 2560
n = gets.chop.to_s
piace_of_one = n.chars.pop

hon = %w(2 4 5 7 9)
pon = %w(0 1 6 8)
bon = %w(3)

if hon.include?(piace_of_one)
  puts "hon"
elsif pon.include?(piace_of_one)
  puts "pon"
else bon.include?(piace_of_one)
  puts "bon"
end


Measured memory_bytes: 14348
#include<bits/stdc++.h>
using namespace std;
long long  arr[10000005];
int main(){
#define int long long 
        int n;
        cin >> n;
        int ans=1;
        for(int i=2;i<=n;i++){
                if(arr[i])
                        continue;
                for(int j=2*i;j<=n;j+=i){
                        int me=j;
                        int cnt=0;
                        while(me%i==0){
                                me/=i;
                                cnt+=1;
                        }
                        cnt+=1;
                        if(arr[j]==0){
                                arr[j]=cnt;
                        }
                        else
                                arr[j]*=cnt;
                }
        }
        for(int i=2;i<=n;i++){
                if(arr[i]){
                        ans+=(i*arr[i]);
                }
                else
                        ans+=(2*i);
        }
        cout << ans << '\n';
}

Measured memory_bytes: 81740
# -*- coding: utf-8 -*-
"""
Created on Wed Mar 25 20:51:57 2020

@author: Kanaru Sato
"""

n = int(input())
h = list(map(int, input().split()))

flag = 0
mh = 10**10

for i in range(n-1):
    if h[n-1-i]-mh <= 1:
        mh = min(mh, h[n-1-i])
    else:
        flag = 1
        break

if flag == 1:
    print("No")
else:
    print("Yes")

Measured memory_bytes: 14396
#include <bits/stdc++.h>
using namespace std;
#define repx(i, a, b) for(int i = a; i < b; i++)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)

int main(){
    
    // 1. 入力情報.
    int A, B, C, O, P, Q, R, S, T;
    scanf("%d %d %d", &A, &B, &C);
    
    // 2. 魔方陣作成.
    // A B O
    // P C Q
    // R S T
    
    // 2-1. 3つの和 を 確認.
    int f = max(A + B, max(B + C, C + A));
    int t = 300;
    
    // 2-2. 魔法陣の候補を絞り込み.
    repx(i, f, t + 1){
        O = i - A - B;
        S = i - B - C;
        T = i - C - A;
        R = i - S - T;
        P = i - A - R;
        Q = i - O - T;
        if(A + C + T == i && O + C + R == i) break;
    }
    
    // 3. 出力.
    printf("%d %d %d\n", A, B, O);
    printf("%d %d %d\n", P, C, Q);
    printf("%d %d %d\n", R, S, T);
    return 0;
}

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

int main() {
  int n, count = 0;
  cin>>n;
  vector<int> s(n);
  for (int i=0;i<n;i++) {
    cin>>s[i];
    if (s[i] != i+1) count++;
  }
  cout<<(count == 0 || count == 2 ? "YES":"NO")<<endl;
}

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

int main(){
    int n,a,b,c,d;
    cin >> n;
    a = n / 1000;
    b = n % 1000 / 100;
    c = n % 100 / 10;
    d = n % 10; 
    if(a+b+c+d == 7) cout << a << "+" << b << "+" << c << "+" << d << "=" << 7 << endl;
    else if(a+b-c+d == 7) cout << a << "+" << b << "-" << c << "+" << d << "=" << 7 << endl;
    else if(a-b+c+d == 7) cout << a << "-" << b << "+" << c << "+" << d << "=" << 7 << endl;
    else if(a+b+c-d == 7) cout << a << "+" << b << "+" << c << "-" << d << "=" << 7 << endl;
    else if(a-b-c+d == 7) cout << a << "-" << b << "-" << c << "+" << d << "=" << 7 << endl;
    else if(a+b-c-d == 7) cout << a << "+" << b << "-" << c << "-" << d << "=" << 7 << endl;
    else if(a-b+c-d == 7) cout << a << "-" << b << "+" << c << "-" << d << "=" << 7 << endl;
    else if(a-b-c-d == 7) cout << a << "-" << b << "-" << c << "-" << d << "=" << 7 << endl;
    return 0;
}

Measured memory_bytes: 256
import math
n=int(input())
A=[]
sum=0
for i in range(n):
  a,s=(int(x) for x in input().split()) 
  A.append((a,s))
for i in A:
  for i2 in A:
    sum+=math.sqrt((i[0]-i2[0])**2+(i[1]-i2[1])**2)
print(sum/n)
 

Measured memory_bytes: 38384
N,M=map(int, raw_input().split())

a=[ [] for i in range(2**3) ]

c={}

for i in range(N):
	x,y,z=map(int, raw_input().split())
	a[0].append(x+y+z)
	a[1].append(x+y-z)
	a[2].append(x-y+z)
	a[3].append(x-y-z)
	a[4].append(-x+y-z)
	a[5].append(-x-y+z)
	a[6].append(-x+y+z)
	a[7].append(-x-y-z)


ans=float("-inf")
for x in a:
	tmp=sum(sorted(x,reverse=True)[:M])
	ans=max(ans, tmp)

print ans


Measured memory_bytes: 32364
#include<bits/stdc++.h>
using namespace std;
typedef		vector<int>				 vi;
typedef 	vector<vi>				vii;
typedef		pair<int,int>			pii;
typedef		unsigned long long		ull;
typedef		long long				ll ;
#define MOD (int)(1e9+7)
#define INF (int)(1<<29) 
#define fori(i,a,b)		for(int i=a ; i <= b ; i++) 			
#define ford(i,a,b)  	for(int i=a ; i >= b ; i-- ) 
#define rep(i,n)   		for(int i=0; i < n ; i++ ) 
#define DEBUG(x)		cout << '>' << #x << ':' << x << endl;


int main()
{
	ios_base::sync_with_stdio(0);	
	int n , m ;
	cin >> n >> m ;
	cout << (n-1)*(m-1) << endl ; 

	return 0 ;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define lson root<<1,l,midd
#define rson root<<1|1,midd+1,r
#define pb push_back
#define ull unsigned long long
#define pii pair<int,int>
#define MP make_pair
typedef long long ll;
const ll INF=1e18;
const int inf=0x3f3f3f3f;
const int M=1e6+6;
const int mod=1e9+7;

int a[M],mp[M];
int main(){
    int n,m;
    scanf("%d",&n);
    int g=0;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),g=__gcd(g,a[i]);
    if(g!=1)
        puts("not coprime");
    else{
        int f=0;
        for(int i=1;i<=n;i++){
            int now=a[i];
            for(int j=2;j*j<=now;j++){
                if(now%j==0){
                    while(now%j==0)
                        now/=j;
                    if(mp[j]==1){
                        f=1;
                        break;
                    }
                    mp[j]=1;
                }
            }
            if(now>1){
                if(mp[now]==1){
                    f=1;
                }
                mp[now]=1;
            }
            if(f)
                break;
        }
        if(!f){
            puts("pairwise coprime");
        }
        else
            puts("setwise coprime");
    }
    return 0;
}


Measured memory_bytes: 7976
N, M=map(int, input().split())
mod=10**9+7
dp=[0 for i in range(N+2)]
dp[N] = 1
is_broken =[False for i in range(N+1)]

for i in range(M):
    a=int(input())
    is_broken[a] = True

for i in reversed(range(N)):
    if is_broken[i]:
        dp[i] = 0
        continue
    dp[i] = (dp[i+1] + dp[i+2]) % mod

print(dp[0])
    

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

bool k = false;
void str(string sa,string sb, string sc, char key) {
  if (key == 'a') {
    if(sa.empty()) k = true; else { key = sa[0]; sa.erase(0,1);  }
  } else if (key == 'b') {
    if(sb.empty()) k = true; else {key = sb[0]; sb.erase(0,1);  } 
  } else {
    if(sc.empty()) k = true; else {key = sc[0]; sc.erase(0,1);  } 
  }
  if (k) {
    key = key - 32;
    cout << key << endl;
  }else {
    str(sa,sb,sc,key);
  }
}
int main(void) {
  string sa, sb, sc;
  cin >> sa >> sb >> sc;
  str(sa,sb,sc,'a');
}

Measured memory_bytes: 3680
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define ALL(a)  (a).begin(),(a).end()

int main(void){
  int N;
  cin >> N;
  vector<int>a(N);
  for(int i=0;i<N;i++){
    cin >> a[i];
  }
  
  sort(a.begin(),a.end());
  
  long long ans = 0;
  
  for(int i=0;i<N-1;i++){
    for(int j=i+1;j<N;j++){
        auto Iter1 = lower_bound(ALL(a), abs(a[i] - a[j]) + 1);
        auto Iter2 = lower_bound(ALL(a), a[i] + a[j]);
        ans += N - (Iter1 - a.begin()) - (a.end() - Iter2);
        if(a[i] > abs(a[i] - a[j]) && a[i] < a[i] + a[j]) ans--;
        if(a[j] > abs(a[i] - a[j]) && a[i] < a[i] + a[j]) ans--;
    }
  }
  
  cout << ans / 3 << endl;
  
  return 0;
}

  

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

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

	int ans = 0;

	ans += abs(a[1] - a[0]);
	ans += abs(a[2] - a[1]);

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,a,b) for (int i = a; i < (b); ++i)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define YY cout << "Yes" << endl;
#define NN cout << "No" << endl;
#define ve vector
#define pint pair<int,int>
const int INF = 1000000007;
const long double EPS = 1e-15;
const long double PI = acos(-1);
typedef long long ll;
using namespace std;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
// *max_element(all(d))
// priority_queue<int,vector<int>,greater<int>>
class cum_sum{
  private:
    vector<long long>sum;
    vector<long long>tmp;
    int n;
  public:
    cum_sum(vector<long long>v):tmp(v),n(v.size()){
      sum.resize(n + 1);
      for(int i = 0; i < n; i++){
        sum[i + 1] = sum[i] + tmp[i];
      }
    };
    long long range_sum(int l, int r){
      if(l > r)swap(l,r);
      return sum[r + 1] - sum[l];
    }
}; 
vector<ll>countt(10000000);
int solve(){
  int n;
  cin >> n;
  vector<ll>v(n);
  map<ll,ll>m;
  rep(i,n){
    cin >> v[i];
    m[v[i]]++;
  }
  for(auto i : m){
    if(i.second > 1){
      ll tmp = i.second;
      ll t = (tmp * (tmp - 1)) / 2;
      countt[i.first] = t;
    }
  }
  cum_sum sum(countt);
  rep(i,n){
    ll tmp = 0;
    if(m[v[i]] > 2){
      tmp += ((m[v[i]] - 1) * (m[v[i]] - 2)) / 2;
    }
    tmp += sum.range_sum(0,v[i] - 1);
    if(v[i] != n)tmp += sum.range_sum(v[i] + 1,n);
    cout << tmp << endl;
  }

  return 0; 
}
int main(){
  // ios::sync_with_stdio(false);cin.tie(nullptr);
  cout << fixed;cout << setprecision(16);
  solve();
  return 0;
}

Measured memory_bytes: 322176
let matrix = Array.init 10 (fun x -> Array.init 10 (fun y -> 0));;

let small x y =
  matrix.(x).(y) <- matrix.(x).(y)+1;
  if x > 0 then matrix.(x-1).(y) <- (matrix.(x-1).(y)+1);
  if y > 0 then matrix.(x).(y-1) <- (matrix.(x).(y-1)+1);
  if x < 9 then matrix.(x+1).(y) <- (matrix.(x+1).(y)+1);
  if y < 9 then matrix.(x).(y+1) <- (matrix.(x).(y+1)+1)
;;

let medium x y =
  small x y;
  if x > 0 then
    begin
      if y > 0 then matrix.(x-1).(y-1) <- (matrix.(x-1).(y-1)+1);
      if y < 9 then matrix.(x-1).(y+1) <- (matrix.(x-1).(y+1)+1);
    end;
  if x < 9 then
    begin
      if y > 0 then matrix.(x+1).(y-1) <- (matrix.(x+1).(y-1)+1);
      if y < 9 then matrix.(x+1).(y+1) <- (matrix.(x+1).(y+1)+1);
    end;
;;

let large x y =
  medium x y;
  if x > 1 then matrix.(x-2).(y) <- (matrix.(x-2).(y)+1);
  if y > 1 then matrix.(x).(y-2) <- (matrix.(x).(y-2)+1);
  if x < 8 then matrix.(x+2).(y) <- (matrix.(x+2).(y)+1);
  if y < 8 then matrix.(x).(y+2) <- (matrix.(x).(y+2)+1)
;;

let () =
  let rec read () =
    try let l = read_line () |> Str.split (Str.regexp ",")
                |> List.map int_of_string
                |> Array.of_list
        in
        if l.(2) = 1 then small l.(0) l.(1)
        else if l.(2) = 2 then medium l.(0) l.(1)
        else large l.(0) l.(1)
        ;read ()
    with End_of_file ->
      let count, max =
        Array.fold_left (fun x1 y1 -> Array.fold_left (fun x2 y2 -> if y2 = 0 then x2+1 else x2) x1 y1) 0 matrix,
        Array.fold_left (fun x1 y1 -> Array.fold_left (fun x2 y2 -> if y2 > x2 then y2 else x2) x1 y1) 0 matrix
      in
      Printf.printf "%d\n%d\n" count max
  in read ()
;;

Measured memory_bytes: 2296
#include<algorithm>
#include<functional>
#include<iostream>

int N;
int A, B, C;
int D[100];

int main()
{
	std::cin >> N >> A >> B >> C;
	for( int i = 0; i != N; ++i )
		std::cin >> D[i];

	std::sort( D, D + N, std::greater<int>() );

	int sum = 0, ans = 0;
	for( int i = 0; i != N; ++i )
	{
		sum += D[i];
		ans = std::max( ans, ( C + sum ) / ( A + ( i + 1 ) * B ) );
	}

	std::cout << ans << std::endl;

	return 0;
}

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

#define ll long long
#define p_q priority_queue
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define str string
#define s_vec(data,name,vertical,horizontal) vector<vector<(data)>> (name)((vertical),vector<(data)>((horizontal)));


int main(){
    int a,b,h;
    cin>>a>>b>>h;
    
    cout<<((a+b)*h)/2<<endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CSharp_practice
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            for (int x = 0; x <= 46299; x++)
            {
                if (Math.Floor(x * 1.08) == n)
                {
                    Console.WriteLine(x);
                    return;
                }
            }
            Console.WriteLine(":(");
        }
    }
}


Measured memory_bytes: 11092
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <random>
#include <complex>
#include <assert.h>

using namespace std;
typedef long long ll;
#define endl '\n'

constexpr ll mod = 1000000007LL;
constexpr ll v_e[] = { 869418286, 727008098, 660103155, 183023413, 471090892, 417297686, 237315285, 542573865, 444014759, 927321758, 184117322, 5655049, 347662323, 346175634, 765144583, 0 };
constexpr ll v_o[] = { 869418286, 727008098, 660103155, 183023413, 471090892, 417297686, 237315285, 542573865, 444014759, 927321758, 184117322, 962779130, 404391958, 700407153, 729548371, 539588932 };

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

	ll T, N, N2, N4, N8; cin >> T;
	ll ans0, ans4,ans8, ans12;
	for (int _t = 0; _t < T; _t++) {
		cin >> N;
		N2 = (N * N) % mod;
		N4 = (N2 * N2) % mod;
		N8 = (N4 * N4) % mod;

		if (N & 1) {// odd
			ans0 = (((v_o[0] * N + v_o[1]) % mod) * N2 + ((v_o[2] * N + v_o[3]) % mod)) % mod;
			ans4 = (((v_o[4] * N + v_o[5]) % mod) * N2 + ((v_o[6] * N + v_o[7]) % mod)) % mod;
			ans8 = (((v_o[8] * N + v_o[9]) % mod) * N2 + ((v_o[10] * N + v_o[11]) % mod)) % mod;
			ans12 = (((v_o[12] * N + v_o[13]) % mod) * N2 + ((v_o[14] * N + v_o[15]) % mod)) % mod;

			cout << (((ans0 * N4 + ans4) % mod) * N8 + ((ans8 * N4 + ans12) % mod)) % mod << endl;
		}
		else {// even
			ans0 = (((v_e[0] * N + v_e[1]) % mod) * N2 + ((v_e[2] * N + v_e[3]) % mod)) % mod;
			ans4 = (((v_e[4] * N + v_e[5]) % mod) * N2 + ((v_e[6] * N + v_e[7]) % mod)) % mod;
			ans8 = (((v_e[8] * N + v_e[9]) % mod) * N2 + ((v_e[10] * N + v_e[11]) % mod)) % mod;
			ans12 = (((v_e[12] * N + v_e[13]) % mod) * N2 + ((v_e[14] * N + v_e[15]) % mod)) % mod;

			cout << (((ans0 * N4 + ans4) % mod) * N8 + ((ans8 * N4 + ans12) % mod)) % mod << endl;
		}
	}

	return 0;
}


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

int main() {
    int x1, x2, x3, x4, y1, y2, y3, y4;
    cin >> x1 >> y1 >> x2 >> y2;
    int x1x2 = x2-x1,
        y1y2 = y2-y1;
    x3 = x2 - y1y2;
    y3 = y2 + x1x2;
    x4 = x1 - y1y2;
    y4 = y1 + x1x2;
    cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;
    return 0;
}

Measured memory_bytes: 3608
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    N, M = LI()
    LR = []
    for _ in range(M):
        LR.append(LI())
    left = 0
    right = INF
    for l, r in LR:
        left = max(left, l)
        right = min(right, r)
    ans = max(right - left + 1, 0)
    return ans

print(main())


Measured memory_bytes: 21168
#include <iostream>

using namespace std;

int main(void)
{
    int a, b;
    
    cin >> a >> b;
    if (a < b)
        cout << "a < b" << endl;
    else if (a > b)
        cout << "a > b" << endl;
    else
        cout << "a == b" << endl;
        
    return 0;
}


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

typedef long long int ll;
typedef vector<int> vi;
typedef vector<vector<int>>vii;
typedef vector<ll> vl;
typedef vector<vector<ll>>vll;
typedef pair <int, int> pii;
typedef pair<ll, ll> pll;

vector<pii> factorize(long long n) 
{ 
    int count = 0; 
    vector<pii> soln;
    // count the number of times 2 divides  
    while (!(n % 2)) { 
        n >>= 1; // equivalent to n=n/2; 
        count++; 
    } 
  
    // if 2 divides it 
    if (count) 
        soln.push_back({2, count});
  
    // check for all the possible numbers that can  
    // divide it 
    for (long long i = 3; i <= sqrt(n); i += 2) { 
        count = 0; 
        while (n % i == 0) { 
            count++; 
            n = n / i; 
        } 
        if (count){
            soln.push_back({i, count});
        } 
            // cout << i << "  " << count << endl; 
    } 
  
    // if n at the end is a prime number. 
    if (n > 2) 
        soln.push_back({n, 1});
    return soln; 
} 


void solve(){
     
    return ;
}

int main(){
    ll n;
    cin>>n;
    vector<pii> prime = factorize(n);
    int sum = 0;
    for(int i =0;i< prime.size();i++){
        // cout<<prime[i].first<<' '<<prime[i].second<<endl;
        int temp = prime[i].second;
        int res = (sqrt(8*temp+1) -1 )/2;
        // cout<<temp<<" "<<res<<endl;
        sum+= res;
    }
    cout<<sum<<endl;
    // cout<<prod<<endl;
    return 0;
}

Measured memory_bytes: 3724
import Control.Applicative
import Control.Monad
import Data.List
import Data.Array

main = do
  [n, m] <- map (read::String -> Int) . words <$> getLine
  arr <- sort <$> forM [1..n] (\i -> do
    [a, b] <- map (read::String -> Int) . words <$> getLine
    return (a, b))
  print . fst $ foldl (\(sumCost, sumDrink) (cost, maxDrink) -> 
    let numDrink = min (m - sumDrink) maxDrink
    in (sumCost + numDrink * cost, sumDrink + numDrink)) (0, 0) arr
  

Measured memory_bytes: 98812
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;
int A[2000001];
int B[2000001];
long C[10001];
long n;
void CountingSort(int k){
	for (long j = 0; j < n; ++j) ++C[A[j]];
	for (long i = 1; i <= k; ++i) C[i] += C[i - 1];
	for (long j = n - 1; j >= 0; --j){
		B[C[A[j]]] = A[j];
		--C[A[j]];
	}
}
int main(){
	scanf("%ld", &n);
	int MAX = -1;
	for (long i = 0; i < n; ++i) scanf("%d", &A[i]);
	for (long i = 0; i < n; ++i) MAX = max(MAX, A[i]);
	CountingSort(MAX);
	for (long i = 1; i <= n; ++i){
		if (i != 1) cout << ' ';
		cout << B[i];
	}
	cout << '\n';
}

Measured memory_bytes: 16908
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <climits>
#include <iomanip>
#include <bitset>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>

using namespace std;

typedef pair <int, int> ii;

const int N = 22;

int n, m;
int ans;
char mat[N][N];

int xx[4] = {-1, +1, +0, +0};
int yy[4] = {+0, +0, -1, +1};

bool in(int x, int y) {
  return (x >= 0 && y >= 0 && x < n && y < m);
}

void go(int sx, int sy) {
  bool used[N][N] = {};
  queue < pair <int, ii> > q;
  q.push({0, {sx, sy}});
  while (!q.empty()) {
    int d = q.front().first, x = q.front().second.first, y = q.front().second.second; q.pop();
    used[x][y] = 1;
    //cout << sx << " " << sy << " " << x << " " << y << " " << ans << endl;
    for (int i = 0; i < 4; i++) {
      int nx = x + xx[i];
      int ny = y + yy[i];
      if (in(nx, ny) && !used[nx][ny] && mat[nx][ny] != '#') {
        used[nx][ny] = 1;
        q.push({d + 1, {nx, ny}});
        ans = max(ans, d + 1);
      }
    }
  }
}

int main() {
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; i++) {
    scanf(" %s", mat[i]);
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (mat[i][j] == '#') continue;
      go(i, j);
    }
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

signed main()
{
    int N; cin>>N;
    vint a(N),b(N),c(N);
    REP(i,N) cin>>a[i];
    REP(i,N) cin>>b[i];
    REP(i,N) cin>>c[i];
    sort(ALL(a));
    sort(ALL(c));

    int ans=0;
    REP(i,N){
        int x=lower_bound(ALL(a),b[i])-a.begin();
        int y=upper_bound(ALL(c),b[i])-c.begin();
        ans+=x*(N-y);
    }
    cout<<ans<<endl;
}


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

int main() {
	int a[102][102];
	int b[102];

	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		for (int i2 = 0; i2 < m; ++i2) {
			cin >> a[i][i2];
		}
	}
	for (int i = 0; i < m; ++i) {
		cin >> b[i];
	}

	for (int i = 0; i < n; ++i) {
		int c = 0;
		for (int i2 = 0; i2 < m; ++i2) {
			c += a[i][i2] * b[i2];
		}
		cout << c << endl;
	}

	return 0;
}

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

int main()
{
  int W, a, b;
  
  cin >> W >> a >> b;
  
  if(abs(b - a) <= W) cout << 0 << endl;
  else cout << min(abs(b - a - W), abs(a - b - W)) << endl;

  return 0;
}


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

def partition_l(A,p,r):
    x = A[r]
    i = p - 1
    for j in range(p,r):
        if A[j] <= x:
            i += 1
            A[i],A[j] = A[j],A[i]

    A[i+1],A[r] = A[r],A[i+1]

    return i+1

b = partition_l(A,0,len(A)-1)
for i,a in enumerate(A):
    if i == b:
        print('[{}] '.format(a),end='')
    elif i < len(A)-1:
        print('{} '.format(a),end='')
    else:
        print('{}'.format(a),end='')
print()



Measured memory_bytes: 16384
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);(i)++)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; }return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; }return 0; }
inline void init() { cout.tie(nullptr); cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }

class unionfind {
    vector<int> par, rank;
    int forest_num;
public:
    unionfind(int n) : par(n), rank(n, 1) {
        forest_num = n;
        for (int i = 0; i < n; i++)par[i] = i;
    }
    void init(int n) {
        par.clear(); par.resize(n);
        rank.clear(); rank.resize(n, 1);
        forest_num = n;
        for (int i = 0; i < n; i++)par[i] = i;
    }
    int root(int x) {
        if (par[x] == x)return x;
        return par[x] = root(par[x]);
    }
    int size(int x) {
        if (par[x] == x)return rank[x];
        return size(par[x]);
    }
    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry)return;
        if (rank[rx] < rank[ry]) {
            par[rx] = ry;
            rank[ry] += rank[rx];
        }
        else {
            par[ry] = rx;
            rank[rx] += rank[ry];
        }
        forest_num--;
    }
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    int fnum() {
        return forest_num;
    }
};

int main() {
    init();

    int n, m;
    cin >> n >> m;

    unionfind uf(m);
    VI k(n);
    vector<VI> l(n);
    FOR(i, 0, n) {
        cin >> k[i];
        l[i].resize(k[i]);
        FOR(j, 0, k[i]) {
            cin >> l[i][j];
            l[i][j]--;
        }
        FOR(j, 1, k[i])uf.unite(l[i][j], l[i][j - 1]);
    }
    map<int, int> ans;
    FOR(i, 0, n)ans[uf.root(l[i][0])]++;
    cout << (ans.size() == 1 ? "YES\n" : "NO\n");
}


Measured memory_bytes: 6912
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <iomanip>
#include <set>
#include <ctime>
#include <tuple>
#include <bitset>
#include <assert.h>
#include <deque>
#include <functional>
using namespace std;
typedef long long ll;

#define fi first
#define se second
#define rep(i, n) for (ll i = 0; i < n; i++)
#define debugA cerr << "AAAAA" << endl
#define debug_ cerr << "-------------" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define debug_vec(v)                   \
    cout << #v << endl;                \
    for (int i = 0; i < v.size(); i++) \
    {                                  \
        cout << v[i] << " ";           \
    }                                  \
    cout << endl;
#define debug_vec2(v)                         \
    cout << #v << endl;                       \
    for (int i = 0; i < v.size(); i++)        \
    {                                         \
        for (int j = 0; j < v[i].size(); j++) \
        {                                     \
            cout << v[i][j] << " ";           \
        }                                     \
        cout << endl;                         \
    }

template <typename T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}

template <typename T>
bool chmin(T &a, const T &b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}

template <typename T>
void quit(T a)
{
    cout << a << endl;
    exit(0);
}

using Graph = vector<vector<int>>;
using P = pair<int, int>;
using P1 = pair<int, pair<int, int>>; // クラスカル法とかで、{cost, {from, to}}的に使う。
const ll LINF = 10010020030040056ll;
const int INF = 1001001001;
const double pi = acos(-1);

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    int MIN = a[0];
    ll ans = 0;
    for (int i = 1; i < n; i++)
    {
        if (MIN <= a[i])
        {
            MIN = a[i];
        }
        else
        {
            ans += MIN - a[i];
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3988
#include <iostream>
#include <string>
#include <algorithm>
#include <regex>
using namespace std;

int main(){
    string S;
    cin >> S;

    int N = S.size();
    long long ans = 0;
    vector<long long> le(N+1, 0);
    vector<long long> ri(N+1, 0);
    for(int i=0;i<N;++i){
        if(S[i] == '<') le[i+1]=max(le[i+1], le[i]+1);
        else le[i+1] = 0;
    }
    for(int i=N-1;i>=0;--i){
        if(S[i] == '>') ri[i]=max(ri[i],ri[i+1]+1);
        else ri[i] = 0;
    }
    for(int i=0;i<=N;++i) ans+=max(le[i],ri[i]);
    cout << ans << endl;
    /*
    int lparNum = 0;
    int rparNum = 0;
    long long ans = 0;

    const regex lre("<+");
    const regex rre(">+");
    smatch m;

    for(size_t i = 0; i < S.size(); i++){
        if(regex_search(S.substr(0, i), m, lre)){
            for(size_t j = 0; j < m.size(); j++){
                lparNum = max(lparNum, (int)m.str(j).size());
            }
        }
        if(regex_search(S.substr(i+1), m, rre)){
            for(size_t j = 0; j < m.size(); j++){
                rparNum = max(rparNum, (int)m.str(j).size());
            }
        }
        cout << "lparNum = " << lparNum << " rparNum : " << rparNum << endl;
        ans += max(lparNum, rparNum);
    }
    cout << ans << endl;
    */
}

Measured memory_bytes: 11648
import fractions
K = int(input())
ans = 0
dp = []
for i in range(0,K+1):
    dpp = []
    for j in range(0,K+1):
        dpp.append(0)
    dp.append(dpp)
def dpgcd(a,b):
    if dp[a][b] != 0:
        return dp[a][b]
    else:
        gg = fractions.gcd(a,b)
        dp[a][b] = gg
        dp[b][a] = gg
        return gg
for i in range(0,K):
    for j in range(0,K):
        g = dpgcd(i+1,j+1)
        for k in range(0,K):
            ans += dpgcd(g,k+1)
print(ans)

Measured memory_bytes: 76108
'use strict';
process.stdin.on('data', function(chunk) {
  var lines = chunk.toString().split('\n');
  var result = (function(data) {
  return Math.pow(data,3);  
  }(parseInt(lines[0],10)
  ));

  console.log(result);
});

process.stdin.resume();
process.stdin.setEncoding('utf8');

Measured memory_bytes: 7644
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
#define INF (1LL << 60)
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,k,n) for(int i=(k);(i)<(n);(i)++)
#define REP(i,n) for(int i = 0;(i)<(n);(i)++)
#define REPR(i,n) for(inti = n; i >= 0; i--)

int main() {
	int n;
	cin >> n;
	vector<int> h(n + 1);
	REP(i, n) {
		cin >> h[i];
	}
	h[n] = 0;
	int ans = 0;
	do{
		int start = n;

		REP(i, n) {
			if (h[i] != 0) {
				start = i;
				break;
			}
		}
		if (start == n) break;

		auto itr = find(h.begin() + start, h.end(), 0);
		int index = distance(h.begin(), itr);
		int min = *min_element(h.begin() + start, itr);
		ans += min;
		FOR(i, start, index) {
			h[i] -= min;
		}
	} while (true);
	cout << ans;
}



Measured memory_bytes: 256
import sys 
import math
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
A, B = map(int, readline().split())
A1 = math.ceil(A * 12.5)
B1 = B * 10
A2 = math.ceil((A+1) * 12.5)
B2 = (B+1) * 10 
a = min(A1,B1)
b = max(A2,B2)
for i in range(a,b+1):
    if A1 <= i < A2 and B1 <= i < B2:
        print(i)
        sys.exit()
print(-1)
        
    

Measured memory_bytes: 9252
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define int long long
#define mkp make_pair
#define pb push_back
#define ff first
#define ss second
#define debug1(a) cout<<a<<endl;
#define debug2(a,b) cout<<a<<' '<<b<<endl;
#define debug3(a,b,c) cout<<a<' '<<b<<' '<<c<<endl;
#define rep(i,n) for(int i=0;i<n;i++)
#define repr(i,a,b)for(int i=a;i<b;i++)
#define repre(i,a,b)for(int i=a;i<=b;i++)
#define clr1(arr) memset(arr,-1,sizeof(arr));
#define clr0(arr) memset(arr,0,sizeof(arr));
#define pi pair<int,int>
#define pii pair<int,pi>
#define all(v) v.begin(),v.end()
#define pq priority_queue
#define mpq priority_queue<int,vector<int>,greater<int> >
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace __gnu_pbds;
using namespace std;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> orderedSet;
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> orderedMSet;
//*p.find_by_order(index) return value at index
//p.order_of_key(key) return index
int32_t main()
{
  //freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);
  fastio
  string a,b;
  cin>>a;
  cin>>b;
  int ans=0;
  rep(i,3)
  {
    if(a[i]==b[i])ans++;
  }
  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
using namespace std;
const int tINF = (int)INT_MAX;
const long long lINF = (long long)LLONG_MAX;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	#ifdef DEBUG
			assert(freopen("inp", "r", stdin));
			assert(freopen("out", "w",stdout));
	#else
			#define cerr if(false)cerr
	#endif
    int n;
    cin >> n;
    string s;
    cin >> s;
    int pos = 0;
    int ans = 0;
    string needle = "ABC";
    while(pos < n && pos != string::npos){
        pos = s.find(needle,pos);
        if(pos != string::npos)
            ++ans;
        else
            break;
        pos += 3;
    }
    cout << ans << '\n';
   cerr << "Time execute: " << (double)clock() / (double)CLOCKS_PER_SEC 
    << " sec" << endl;
}

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

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

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

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

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

  LL Q, H, S, D, N;
  cin >> Q >> H >> S >> D >> N;

  LL x1 = min({Q*4, 2*H, S});
  LL x2 = min({x1*2, D});
  cout << N/2*x2 + (N%2? x1:0) << endl;

  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#define N 200001
int a[N],i,l,n,r,o[N],p[N],q;
inline bool check(int s)
{
	if(s==1)
	{
		for(i=1;i<n;i++)if(a[i]>=a[i+1])return false;
		return true;
	}
	for(i=1,q=0;i<=n;i++)
	if(o[q]<a[i])o[++q]=a[i],p[q]=1;
	else
	{
		while(a[i]<o[q])q--;
		if(o[q]!=a[i])o[++q]=a[i],p[q]=2;
		else if(p[q]!=s)p[q]++;
		else
		{
			for(;o[q-1]+1==o[q]&&p[q-1]==s;q--);
			if(o[q-1]+1==o[q]&&q==1)return false;
			else if(o[q]==o[q-1]+1)p[q-1]++,o[q]=a[i],p[q]=1;
			else o[q]--,p[q]=2,o[++q]=a[i],p[q]=1;
		}
	}
	return true;
}
int main()
{
	scanf("%d",&n),l=1,r=n;
	for(i=1;i<=n;i++)scanf("%d",a+i);
	while(l<r)check(l+r>>1)?r=l+r>>1:l=l+r+2>>1;
	return 0*printf("%d\n",l);
}

Measured memory_bytes: 2560
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

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

    int front = 0;
    int cnt = 0;
    for(int i=0; i<n; ++i){
        if(s[i] == '('){
            ++ cnt;
        }
        else{
            if(cnt == 0)
                ++ front;
            else
                -- cnt;
        }
    }

    s = string(front, '(') + s + string(cnt, ')');
    cout << s << endl;

    return 0;
}


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

arr = [0 for i in range(N+2)]

for i in range(M):
  l,r = map(int,input().split())
  arr[l] += 1
  arr[r+1] -= 1
  
for i in range(1,len(arr)):
  arr[i]+=arr[i-1]

cnt = 0

for i in range(len(arr)):
  if arr[i] >= M:
    cnt += 1
print(int(cnt))

Measured memory_bytes: 45216
#include <iostream>
#include <vector>
#include <tuple>
#include <queue>

template <class T>
std::vector<T> vec(int len, T elem) { return std::vector<T>(len, elem); }

template <class T>
using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template <class Cost = int>
struct Edge {
    int src, dst;
    Cost cost;
    Edge(int src = -1, int dst = -1, Cost cost = 1)
        : src(src), dst(dst), cost(cost){};

    bool operator<(const Edge<Cost>& e) const { return this->cost < e.cost; }
    bool operator>(const Edge<Cost>& e) const { return this->cost > e.cost; }
};

template <class Cost = int>
struct Graph {
    std::vector<std::vector<Edge<Cost>>> graph;

    Graph(int n = 0) : graph(n) {}

    void span(bool direct, int src, int dst, Cost cost = 1) {
        graph[src].emplace_back(src, dst, cost);
        if (!direct) graph[dst].emplace_back(dst, src, cost);
    }

    int size() const { return graph.size(); }
    void clear() { graph.clear(); }
    void resize(int n) { graph.resize(n); }

    std::vector<Edge<Cost>>& operator[](int v) { return graph[v]; }
    std::vector<Edge<Cost>> operator[](int v) const { return graph[v]; }
};

constexpr int INF = 1 << 29;

bool solve() {
    int n, m, k, s, t;
    std::cin >> n >> m >> k >> s >> t;
    if (n == 0) return false;
    --s;

    auto dss = vec(n, vec(n, INF));
    while (m--) {
        int u, v, c;
        std::cin >> u >> v >> c;
        --u, --v;
        dss[u][v] = dss[v][u] = c;
    }
    for (int v = 0; v < n; ++v) dss[v][v] = 0;

    for (int v = 0; v < n; ++v) {
        for (int u = 0; u < n; ++u) {
            for (int w = 0; w < n; ++w) {
                dss[u][w] = std::min(dss[u][w], dss[u][v] + dss[v][w]);
            }
        }
    }

    std::vector<int> vs(k), cs(k);
    for (int i = 0; i < k; ++i) {
        std::cin >> vs[i] >> cs[i];
        --vs[i];
    }
    vs.push_back(s);

    auto ndss = vec(k + 1, vec(k + 1, t + 1));
    for (int i = 0; i <= k; ++i) {
        for (int j = 0; j <= k; ++j) {
            ndss[i][j] = dss[vs[i]][vs[j]];
        }
    }

    auto dist = vec(k + 1, vec(1 << k, t + 1));
    dist[k][0] = 0;
    MinHeap<std::tuple<int, int, int>> que;
    que.emplace(0, k, 0);

    while (!que.empty()) {
        int i, b, d;
        std::tie(d, i, b) = que.top();
        que.pop();
        if (d > dist[i][b]) continue;

        for (int j = 0; j <= k; ++j) {
            int nd = d + ndss[i][j];
            if (dist[j][b] <= nd) continue;
            dist[j][b] = nd;
            que.emplace(nd, j, b);
        }

        if (i < k && ((b >> i) & 1) == 0) {
            int nb = b | (1 << i);
            int nd = d + cs[i];
            if (dist[i][nb] <= nd) continue;
            dist[i][nb] = nd;
            que.emplace(nd, i, nb);
        }
    }

    int ans = 0;
    for (int b = 0; b < (1 << k); ++b) {
        if (dist[k][b] <= t) ans = std::max(ans, __builtin_popcount(b));
    }

    std::cout << ans << "\n";
    return true;
}

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

    while (solve()) {};

    return 0;
}



Measured memory_bytes: 27208
#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
typedef long long ll;
const int N=4e2+5;
int arr[N],n;
ll memo[N][N],pre[N];
ll dp(int i,int j)
{
    //printf("%d %d\n",i,j);

    if(i==j)
        return 0;


    ll &ret=memo[i][j];
    if(~ret)
        return ret;
    ret=1e17;
    for(int k=i;k<j;++k)
    {
        ret=min(ret,dp(i,k)+dp(k+1,j)+pre[j]-pre[i-1]);

    }

    return ret;

}
int main()
{
    memset(memo,-1 ,sizeof memo);
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        int a;
        scanf("%d",&a);
        pre[i]=pre[i-1]+a;
    }
    ll sol=dp(1,n);
    printf("%lld\n",sol);


    return 0;
}


Measured memory_bytes: 5072
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector> 
#define N 200005
using namespace std;
typedef long long ll;
const ll inf=1e12;
struct P{
	ll a,b;
	P(){}
	P(ll x,ll y){a=x;b=y;}
}a[N],b[N];
vector<P> v[N];
int n,son[N][2];
ll w[N][2],mid,g[N];
void dfs(int k){
	v[k].clear();
	if(!son[k][0]){
		v[k].push_back(P(0,0));
		return;
	}
	int l=son[k][0],r=son[k][1];
	ll lim=mid-w[k][0]-w[k][1],wl=w[k][0],wr=w[k][1];
	if(lim<0) return;
	dfs(l);
	dfs(r);
	if(v[l].size()>v[r].size()) swap(l,r),swap(wl,wr);
	int vl=v[l].size(),vr=v[r].size();
	ll mn=inf;int tota=0,totb=0;
	for(int i=0,pos=0;i<vl;i++){
		while(pos<vr&&v[l][i].b+mn>lim) {mn=min(mn,v[r][pos].a);pos++;}
		if(v[l][i].b+mn>lim) break;
		a[++tota]=P(v[l][i].a+wl,v[r][pos-1].b+wr);
	}
	mn=inf;
	for(int i=0;i<vl;i++) g[i]=inf; 
	for(int i=0,pos=0;i<vr;i++){
		while(pos<vl&&v[r][i].b+mn>lim){mn=min(mn,v[l][pos].a);pos++;}
		if(v[r][i].b+mn>lim) break;
		g[pos-1]=min(g[pos-1],v[r][i].a+wr);
	}
	for(int i=0;i<vl;i++) if(g[i]!=inf) b[++totb]=P(g[i],v[l][i].b+wl);
	int L=1,R=1;
	while(L<=tota||R<=totb){
		if(R>totb||(L<=tota&&a[L].b<b[R].b)){
			v[k].push_back(a[L]);L++;
		}else v[k].push_back(b[R]),R++;
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1,x,val;i<n;i++){
		scanf("%d%d",&x,&val);
		if(!son[x][0]) son[x][0]=i+1,w[x][0]=val;
		else son[x][1]=i+1,w[x][1]=val;
	}
	ll l=0,r=inf,ans;
	while(l<=r){
		mid=l+r>>1;
		dfs(1);
		if(v[1].size()) ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%lld",ans);
	return 0;
} 

Measured memory_bytes: 37856
//template code, C343, 2019
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Iterator;

class Graph {
    private int totalVertex;
    private LinkedList<LinkedList<Integer>> adjList;
    //adjacency list of edges
    public Graph() { totalVertex = 0; }
    public void loadAdjList() {
        Scanner in = new Scanner(System.in);
        totalVertex = in.nextInt();
        adjList = new LinkedList<LinkedList<Integer>>();
        for(int i = 0; i < totalVertex; i ++) {
            LinkedList<Integer> tmp = new LinkedList<Integer>();
            int idx1 = in.nextInt() - 1;
            int degree = in.nextInt();
            //System.out.println("mark idx1 = " + idx1 + " degree = " + degree);
            for(int j = 0; j < degree; j ++) {
                int idx2 = in.nextInt() - 1;
                tmp.add(idx2);
            }
            adjList.add(tmp);
        }
        in.close();
    }
    public void printAdjMatrix() {
        Integer[][] adjMatrix = new Integer[totalVertex][totalVertex];
        //complete the following
        for(int i = 0; i < adjMatrix.length; i++){
            for(int j = 0; j < adjMatrix[i].length; j++){
                LinkedList<Integer> edges = adjList.get(i);
                if(edges.contains(j))
                    adjMatrix[i][j] = 1;
                else
                    adjMatrix[i][j] = 0;
            }
        }

        for (Integer[] adjMatrix1 : adjMatrix) {
            for (int j = 0; j < adjMatrix1.length; j++){
                if (j == adjMatrix1.length - 1)
                    System.out.print(adjMatrix1[j]);
                else
                    System.out.print(adjMatrix1[j] + " ");
            }
            
            System.out.println();
        }
    }
}

//change class name GraphRepresentation to Main() for submission to AIZU
public class Main {
    public static void main(String argv[]) {
        Graph g = new Graph();
        g.loadAdjList();
        g.printAdjMatrix();
    }
}


Measured memory_bytes: 33048
import sys
n = int(sys.stdin.readline())
L = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

p = [[0 for _ in range(3)] for _ in range(n)]

p[0] = L[0].copy()
#print(p)
#print(L)

for d in range(1, n):
    for i in range(3):
        if i ==0:
            p[d][0] = max(p[d-1][1], p[d-1][2]) + L[d][0]
        elif i ==1:
            p[d][1] = max(p[d-1][0], p[d-1][2]) + L[d][1]
        elif i==2:
            p[d][2] = max(p[d-1][0], p[d-1][1]) + L[d][2]

print(max(p[-1]))

Measured memory_bytes: 47280
#include <iostream>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <limits>
#include <numeric>
#include <algorithm>
#include <functional>

using namespace std;

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

	int A, B, C;
	cin >> A >> B >> C;

	cout << (A * B) / 2;

	return 0;
}


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


int main(void){
    
    int x,a,b,c;
    cin >> a >> b >> c >> x;
    int i,j,k,cnt=0;
    for(i=0;i<=a;++i){
        for(j=0;j<=b;++j){
            for(k=0;k<=c;++k){
                if( 500*i+100*j+50*k == x )cnt++;
            }
        }
    }
    cout << cnt;
    
    
    return 0;
    
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 1000000000000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;





int main(){

	int A,B;
	scanf("%d %d",&A,&B);

	if(A >= 13){

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

	}else if(A >= 6){

		printf("%d\n",B/2);
	}else{

		printf("0\n");
	}

	return 0;
}


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

int main()
{
    long long n,i,j,cnt=0,m,x;
    long long sum=0;
    long long s=0;
    vector<long long>v;
    //vector<long long>v2;
    cin>>n>>m;
    for(i=0;i<n;i++)
    {
        cin>>x;
        v.push_back(x);
        //sum+=x;
    }
    v[0]=v[0]%m;
    for(i=1;i<n;i++)
    {
       v[i]+=(v[i-1]%m);
       v[i]=v[i]%m;
       //cout<<v[i]<<" ";

    }
    sort(v.begin(),v.end());
    //if(v[0]==0)
        //cnt++;
    for(i=0;i<v.size();i++)
    {
       // cout<<v[i]<<" ";
        if(v[i]==0)
            cnt++;
        if(i>0 && v[i]==v[i-1])
            s++;
        else
            s=0;
        cnt+=s;
    }
    cout<<cnt<<"\n";
    return 0;
}


Measured memory_bytes: 1400
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long ll;
#define INF 100000000
#define MOD 1000000007

int main()
{
	const int N = 50;
	int n, m;
	int road[N] = {0};
	
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;

		road[a - 1]++;
		road[b - 1]++;
	}
	for (int i = 0; i < n; i++) {
		cout << road[i] << endl;
	}

	return (0);
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<queue>
#include<set>
#include<vector>
#include<stack>
#include<map>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

#define mod 998244353
#define inf 0x7f7f7f7f
#define maxn 500005
#define N 300005
typedef long long ll;

inline int read()
{
    int x = 0;
    int f = 1;
    char c = getchar();
    while (c<'0' || c>'9')
    {    
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0'&&c <= '9')
    {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x*f;
}

//_scc[u]存u点所在强连通分量的标号,out[x]存标号为x的强连通分量的出度,
//cot[x]存标号为x的连通量的点的数目
int n, x, cnt, k;
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        if (x >= k) cnt++;
    }
    cout << cnt << endl;
}   

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

using namespace std;

const int INF = 1<<29;

int main(){
  int n, m;
  while(cin >> n >> m && (n|m)){
    vector<int> C(m);
    for(int i=0; i<m; i++) cin >> C[i];
    
    vector<int> dp(256, INF);
    dp[128] = 0;
    while(n--) {
      vector<int> next(256, INF);
      int in; cin >> in;
      for(int i=0; i<=255; i++){
	if(dp[i] < INF) {
	  for(int j=0; j<m; j++){
	    int now = i + C[j];
	    if(now < 0)   { now = 0;   }
	    if(now > 255) { now = 255; }
	    int diff = (in - now) * (in - now);
	    next[now] = min(next[now], dp[i] + diff );
	  }
	}
      }
      dp = next;
    }
    
    cout << *min_element(dp.begin(), dp.end()) << endl;
  }
  return 0;
}

Measured memory_bytes: 1216
#include <iostream>
#include <set>

using namespace std;

int main() {

    int nn;
    set<int> stt;
    cin >> nn;
    for (int i = 0; i < nn; i ++){
        int xx; cin >> xx;
        if (stt.find(xx) != stt.end()){
            cout << "NO" << endl;
            return 0;
        }
        stt.insert(xx);
    }
    cout << "YES" << endl;
    return 0;
}


Measured memory_bytes: 9600