akhauriyash/Code-Regression huggingface dataset:
use self::union_find::UnionFind;
use proconio::input;
use proconio::marker::Usize1;

fn main() {
    input! {
        n: usize,
        k: usize,
        l: usize,
        pq: [(Usize1, Usize1); k],
        rs: [(Usize1, Usize1); l],
    };
    let mut uf1 = UnionFind::new(n);
    for &(p_i, q_i) in pq.iter() {
        uf1.unite(p_i, q_i);
    }
    let mut uf2 = UnionFind::new(n);
    for &(r_i, s_i) in rs.iter() {
        uf2.unite(r_i, s_i);
    }
    let mut map = std::collections::BTreeMap::new();
    for i in 0..n {
        *map.entry((uf1.root(i), uf2.root(i))).or_insert(0) += 1;
    }
    for i in 0..n {
        print!(
            "{}{}",
            map.get(&(uf1.root(i), uf2.root(i))).unwrap_or(&0),
            if i == n - 1 { "\n" } else { " " }
        );
    }
}

mod union_find {
    pub struct UnionFind {
        p: Vec<usize>,
        s: Vec<usize>,
    }

    impl UnionFind {
        pub fn new(n: usize) -> Self {
            let mut p = vec![0; n];
            for i in 0..n {
                p[i] = i;
            }
            let s = vec![1; n];
            Self { p, s }
        }

        pub fn root(&mut self, x: usize) -> usize {
            if self.p[x] == x {
                return x;
            } else {
                self.p[x] = self.root(self.p[x]);
                self.p[x]
            }
        }

        pub fn unite(&mut self, x: usize, y: usize) {
            let rx = self.root(x);
            let ry = self.root(y);
            if rx == ry {
                return;
            };
            if self.s[rx] >= self.s[ry] {
                self.s[rx] += self.s[ry];
                self.p[ry] = rx;
            } else {
                self.s[ry] += self.s[rx];
                self.p[rx] = ry;
            }
        }
    }
}


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

int main() {
    ll n; cin >> n;
    vector<ll> h(n);
    rep(i, n) cin >> h[i];
    vector<ll> dp(n, INF);
    dp[0] = 0;
    dp[1] = abs(h[0] - h[1]);
    for (int i=2; i<n; ++i) { 
        dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]), dp[i-2] + abs(h[i] - h[i-2]));
    }
    cout << dp[n-1] << endl;
}

Measured memory_bytes: 1792
fun main(args: Array<String>) {
    val fiveHandledYenCnt = readLine()!!.toInt()
    val handledYenCnt = readLine()!!.toInt()
    val fiftyYenCnt = readLine()!!.toInt()
    val amount = readLine()!!.toInt()

    var answer = 0
    for (fh in 0..fiveHandledYenCnt) {
        var fhAmount = fh * 500
        for(h in 0..handledYenCnt) {
            var hAmount = h * 100
            for (f in 0..fiftyYenCnt) {
                var fAmount = f * 50
                if (fhAmount + hAmount + fAmount == amount) {
                    answer += 1
                }
            }
        }
    }
    print(answer)
}

Measured memory_bytes: 31740
#include <bits/stdc++.h>
#define fol(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
        int n;cin>>n;
        int a,ans=1;
        fol(j,n){
            cin>>a;
            if(a%2) ans*=1;
            else ans *= 2;
        }
        ans = pow(3,n)-ans;
        cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
from math import gcd
from numba import jit

@jit
def calc(): 
  k=int(input())
  ans=0
  for a in range(1,k+1):
    for b in range(1,k+1):
      d=gcd(a,b)
      for c in range(1,k+1):
        ans+=gcd(d,c)
  print(ans)
calc()

Measured memory_bytes: 111960
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	
	public static void insert(ArrayList<Integer> list, int x) {
		list.add(x);
		sendUp(list, list.size() - 1);
	}
	private static void sendUp(ArrayList<Integer> list, int x) {
		int parent = (x-1)/2;
		if(parent >= 0)
			if(list.get(parent) < list.get(x)) {
				int temp = list.get(x);
				list.set(x, list.get(parent));
				list.set(parent, temp);
				sendUp(list, parent);
			}
				
	}
	
	public static void extractMax(ArrayList<Integer> list) {
		System.out.println(list.get(0));
		list.set(0, list.get(list.size()-1));
		list.remove(list.size()-1);
		maxHeapify(list, 0);
	}
	private static void maxHeapify(ArrayList<Integer> a, int x) {
		int left = 2 * x + 1;
		int right = 2 * x + 2;
		int largest = x;
		if(left < a.size())
			if(a.get(left) > a.get(x))
				largest = left;
		if(right < a.size())
			if(a.get(right) > a.get(largest))
				largest = right;
		if(largest != x) {
			int temp = a.get(x);
			a.set(x, a.get(largest));
			a.set(largest, temp);
			maxHeapify(a, largest);
		}
	}
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		ArrayList<Integer> a = new ArrayList<Integer>();
		String next = in.next();
		while(!next.equals("end")) {
			if(next.equals("insert")) {
				insert(a, in.nextInt());
				next = in.next();
			} else {
				extractMax(a);
				next = in.next();
			}
		}
		in.close();
	}
}



Measured memory_bytes: 483492
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		String S = scan.next();
		String str = S;
		
        for(int i = 1; i <= S.length(); ++i) {
    		
        	if(i % 2 == 1 && str.startsWith("L")) {
        		
        		System.out.println("No");
        		scan.close();
        		return;
        		
        	} else if(i % 2 == 0 && str.startsWith("R")) {

        		scan.close();
        		System.out.println("No");
        		return;
        		
        	}
        	
        	str = str.substring(1);
        }
		
		System.out.println("Yes");
		
		scan.close();
	}

}


Measured memory_bytes: 21844
#include <stdio.h>

#define MAX 44

int fib(int);


int main() {
    
    int n;
    
    scanf("%d",&n);
    
    if(n==0 || n==1) printf("1\n");
    if(n>1) printf("%d\n",fib(n));
    
    return 0;
}


int fib(int x) {
    
    int i,F[MAX];
    
    F[0] = 1;
    F[1] = 1;
    for(i=2; i<=x; i++) F[i] = F[i-1]+F[i-2];
    
    return F[x];
}

Measured memory_bytes: 596
#!/usr/bin/python
# -*- coding: utf-8 -*-
from collections import deque


class EndLoop(Exception):
    pass


def solve():
    while 1:
        try:
            N, M = list(map(int, input().split(" ")))
            Deque1 = deque()
            DequeN = deque()
            edges_1 = [False] * N
            edges_N = [False] * N
            Deque1.extend(edges_1)
            DequeN.extend(edges_N)

            for _ in range(M):
                a, b = list(map(int, input().split(" ")))
                if a == 1:
                    Deque1[b - 1] = True
                elif b == 1:
                    Deque1[a - 1] = True
                elif a == N:
                    DequeN[b - 1] = True
                elif b == N:
                    DequeN[a - 1] = True
                else:
                    pass

            for i in range(N):
                if Deque1[i] == True and DequeN[i] == True:
                    print("POSSIBLE")
                    raise EndLoop

            print("IMPOSSIBLE")
            break
        except:
            break


solve()

Measured memory_bytes: 54920
N = int(input())
h = list(map(int, input().split()))

"""
# 貰うDP
# DP配列全体を初期化
dp = [float("inf")] * N
# 初期条件を入力
dp[0] = 0
dp[1] = abs(h[1] - h[0])

# ループを回す
for i in range(2, N):
    dp[i] = min(dp[i - 2] + abs(h[i] - h[i - 2]), dp[i - 1] + abs(h[i] - h[i - 1]))
"""

# 貰うDP
# DP配列全体を初期化
dp = [float("inf")] * N
# 初期条件を入力
dp[0] = 0

# ループを回す
for i in range(N - 1):
    if i == N - 2:
        dp[i + 1] = min(dp[i + 1], dp[i] + abs(h[i] - h[i + 1]))
    else:
        dp[i + 1] = min(dp[i + 1], dp[i] + abs(h[i] - h[i + 1]))
        dp[i + 2] = min(dp[i + 2], dp[i] + abs(h[i] - h[i + 2]))


# DPテーブルから解を出力
print(dp[N - 1])


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

int main() {
  ll X = 0, Y = 0,count = 0;
  cin >> X >> Y;
  while(X <= Y){
    X *= 2;
    count++;
  }
  cout << count;
}

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

#define rep(i, m, n) for(int(i) = (int)(m); i < (int)(n); ++i)
#define rep2(i, m, n) for(int(i) = (int)(n)-1; i >= (int)(m); --i)
#define REP(i, n) rep(i, 0, n)
#define REP2(i, n) rep2(i, 0, n)
#define all(hoge) (hoge).begin(), (hoge).end()
#define en '\n'
using ll = long long;
using ull = unsigned long long;
template <class T>
using vec = vector<T>;
template <class T>
using vvec = vector<vec<T>>;
typedef pair<ll, ll> P;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
constexpr long long MOD = (ll)1e9 + 7;
//constexpr long long MOD = 998244353LL;
using ld = long double;
static const ld pi = 3.141592653589793L;
typedef vector<ll> Array;
typedef vector<Array> Matrix;

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

struct Edge {
    ll to, rev;
    long double cap;
    Edge(ll _to, long double _cap, ll _rev) {
        to = _to;
        cap = _cap;
        rev = _rev;
    }
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

void add_edge(Graph &G, ll from, ll to, long double cap, bool revFlag,
              long double revCap) {
    G[from].push_back(Edge(to, cap, (ll)G[to].size()));
    if(revFlag)
        G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

void solve() {
    ll n, m, d;
    cin >> n >> m >> d;

    if(d) {
        cout << fixed << setprecision(10) << (long double)(n - d) * 2.0L * (long double)(m - 1) / (long double)(n * n) << en;
    } else {
        cout << fixed << setprecision(10) << (long double)(n - d) * (long double)(m - 1) / (long double)(n * n) << en;
    }
}

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

    solve();
    // ll t;cin>>t;REP(i,t) solve();

    return 0;
}


Measured memory_bytes: 3776
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll LINF = 1e18;
const int INF = 1e9;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main(){
    int N;
    cin>>N;
    int Fp[N],Fm[N];
    rep(i,N){
        int x,y; cin>>x>>y;
        Fm[i]=x-y;
        Fp[i]=x+y;
    }
    sort(Fm,Fm+N);
    sort(Fp,Fp+N);
    cout<<max(Fm[N-1]-Fm[0], Fp[N-1]-Fp[0])<<endl;
    return 0;
}

Measured memory_bytes: 5188
#include <iostream>
#include <string>

using namespace std;

int main(){
  string S;
  int N;
  cin >> N >> S;
  size_t l = S.length();

  for(int i = 0; i < l; i++){
    int x = S[i] - 'A';
    x = (x + N) % 26;
    cout << char('A' + x);
  }
  cout << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<iostream>
#include<sstream>
#include<utility>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#include<stack>
#include<functional>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

int main()
{
	string s,t;
	cin>>s>>t;
	sort(s.begin(),s.end() );
	sort(t.begin(),t.end(),greater<char>());
	cout<<(s<t?"Yes":"No")<<endl;
}


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

using namespace std;

#define ll long long

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

    int n, m;
    cin >> n >> m;
    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n);
    ll res = 0;
    for (int i = 0; i < n - m; i++) {
        res += a[i];
    }
    cout << res << "\n";
    return 0;
}

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


int main(){
  ll N;
  cin >> N;
  string ans;
  while(N>0){
    ll t = N%26;
    if(t==0){
      ans = 'z' + ans;
    }else{
      ans = char('a'+(t-1)) + ans;
    }
    N/=26;
    if(t==0)N--;
  }
  cout << ans << endl;

}


Measured memory_bytes: 3564
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int arr[n];
    for(int i=0;i<n;i++)
        cin >> arr[i];
    sort(arr,arr+n);
    cout << arr[n/2]-arr[n/2-1];
}


Measured memory_bytes: 640
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>

using namespace std;

typedef pair<long long int, long long int> P;
long long int INF = 1e18;

int main(){
	
	int a, b;
	cin >> a >> b;
	
	int ret = b - a;
	
	for(int i = 0; i <= ret; i++){
		b -= i;
	}
	
	cout << -b << endl;
	
	return 0;
}

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

int32_t main() {
    int n, W;
    cin >> n >> W;

    vector<int> dp(W + 1, 0);

    for (int i = 0; i < n; ++i) {
        int w, v;
        cin >> w >> v;

        for (int j = W - w; j >= 0; --j) {
            dp[j + w] = max(dp[j + w], dp[j] + v);
        }
    }

    cout << dp[W] << "\n";
}

Measured memory_bytes: 1024
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
//ll mod = 998244353;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main() {
    int x;
    cin >> x;
    if (x == 1) {
        cout << 1 << endl;
        return 0;
    }
    int ans = 0;
    for (int i = 2; i * i <= x; ++i) {
        int num = i;
        bool flg = false;
        while(1) {
            if (num * i > x) {
                if (flg) ans = max(ans, num);
                break;
            }
            num *= i;
            flg = true;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3604
<?php

$s=new Scanner();

$h=$s->nextInt();
$w=$s->nextInt();
//here..!

for($i=0;$i<$h+2;$i++){

  for($j=0;$j<$w+2;$j++){
    $grid[$i][$j]=".";
    $gridNum[$i][$j]=0;
  }
}



for($i=1;$i<$h+1;$i++){
  $str=$s->next();
  $char=str_split($str);

  for($j=1;$j<$w+1;$j++){
    $grid[$i][$j]=$char[$j-1];
  }
}



for($i=1;$i<$h+1;$i++){
  for($j=1;$j<$w+1;$j++){
    //1
    if($grid[$i-1][$j-1]=='#'){
      $gridNum[$i][$j]++;
    }
    //2
     if($grid[$i-1][$j]=='#'){

      $gridNum[$i][$j]++;
    }
    //3
     if($grid[$i-1][$j+1]=='#'){

      $gridNum[$i][$j]++;
    }
    //4
     if($grid[$i][$j-1]=='#'){

      $gridNum[$i][$j]++;
    }
    //5
     if($grid[$i][$j+1]=='#'){

      $gridNum[$i][$j]++;
    }
    //6
     if($grid[$i+1][$j-1]=='#'){

      $gridNum[$i][$j]++;
    }
    //7
     if($grid[$i+1][$j]=='#'){

      $gridNum[$i][$j]++;
    }
    //8
     if($grid[$i+1][$j+1]=='#'){

      $gridNum[$i][$j]++;
    }
    

    if($grid[$i][$j]=='#'){
      $result.='#';
      if($j==$w) {
        $result.=PHP_EOL;
      } 
    }
    else{
      $result.=(string)$gridNum[$i][$j];
      if($j==$w) {
        $result.=PHP_EOL;
      }  
    }
  }
}
echo $result.PHP_EOL;




class Scanner{
  private $arr = [];
  private $count = 0;
  private $pointer = 0;
 
  public function next() {
    if ($this->pointer >= $this->count) {
      $str = trim(fgets(STDIN));
      $this->arr = explode(' ', $str);
      $this->count = count($this->arr);
      $this->pointer = 0;
    }
    $result = $this->arr[$this->pointer];
    $this->pointer++;
    return $result;
  }
  public function hasNext(){
    return $this->pointer < $this->count;
  }
  public function nextInt(){
    return (int)$this->next();
  }
  public function nextDouble(){
    return (double)$this->next();
  }
}

#$B2~9T$"$j$NI8=`=PNO%/%i%9(B
class out{
  public static function println($str = ""){
    echo ($str . PHP_EOL);
  }

  #$BH>3Q6h@Z$j$G$NJQ?t$N=PNO(B
  public static function printVar(){
    $params = func_get_args();
    foreach ($params as $param) {
      echo ($param." ");
    }
    echo PHP_EOL;
  }
}


Measured memory_bytes: 4728
#include <bits/stdc++.h>
using namespace std;
#define ALL(A) (A).begin(),(A).end()
#define ll long long
const ll mod = 1e9+7;
const ll INF = 2*1e18;
const int inf = 1e9+7;

int main(void){
	int N;
	cin >> N;
	int ans = 0;
	for(int i=1;i<=N;i++){
		string t;
		t = to_string(i);
		if(t.size()%2==1)ans++;
	}
	cout << ans << endl;
}

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

int main(){
  int n;
  cin >> n;
  vector<pair<pair<string,int>,int>> p(n);
  for(int i=0; i<n; i++){
    string town;
    int point;
    cin >> town >> point;
    p[i]=make_pair(make_pair(town,-point),i);
  }
  sort(p.begin(),p.end());
  for (auto e : p){
    cout << e.second+1 << endl;
  }
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void)
{
    int n;
    scanf("%d",&n);
    int l[n];
    int r[n];
    for(int p=0;p<n;p++)
    {
        scanf("%d %d",&l[p],&r[p]);
    }
    int ans=0;
    for(int q=0;q<n;q++)
    {
        ans+=r[q];
        ans-=l[q];
    }
    ans +=n;
    printf("%d",ans);
}


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

int main()
{
	int n;
	string s,t,ans;
    cin>>n>>s>>t;
    
    for(int i=0; i<n; i++)
	{
        ans+=s[i];
        ans+=t[i];
    }
    
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int m,f,b,ans;
  cin>>m>>f>>b;
  if(b-m<=0){
    cout<<"0"<<endl;
  }else if(b<=m+f){
    ans=b-m;
    cout<<ans<<endl;
  }else{
    cout<<"NA"<<endl;
  }
  return 0;
}

Measured memory_bytes: 3092
#include <stdio.h>
int main(){
  char c;
  int a=0;
  char f=0;
  while(getchar()!=10);
  while((c=getchar())!=10){
    if(c=='A'){
      f='A';
    }else if(c=='B'){
      if(f=='A') f='B'; else f=0;
    }else if(c=='C'){
      if(f=='B') a++;
      f=0;
    }else{
      f=0;
    }
  }
  printf("%d\n", a);
}


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

int main(){
  int N;
  cin >> N;
  vector<int> a(N);
  rep(i,N){
    cin >> a.at(i);
    --a.at(i);
  }
  int cnt=0;
  rep(i,N){
    if(a.at(a.at(i))==i){
      ++cnt;
    }
  }
  cout << cnt/2 << endl;
}

Measured memory_bytes: 640
#include <stdio.h>
#include <string.h>

typedef struct Word
{
    char	word[30];
    int		page;
} WORD;

WORD wordArray[100];

void input(char *, int);
	int is_smaller(char *, int, int);

void output(WORD *);

int main()
{
	char	tempWord[30];
    int		tempPage;
	
	while(scanf("%s %d", tempWord, &tempPage) != EOF)
    	input(tempWord, tempPage);
    
    output(wordArray);
	
	return 0;
}

void input(char *input_word, int input_page)
{
	int cnt1, cnt2;
	
	for(cnt1 = 0; cnt1 < 100; cnt1++)
	{
		if(wordArray[cnt1].page == 0)
		{
			wordArray[cnt1].page = input_page;
			strcpy(wordArray[cnt1].word, input_word);
			break;
		}
		else if(is_smaller(input_word, input_page, cnt1))
		{
			for(cnt2 = 98; cnt2 >= cnt1; cnt2--)
			{
				strcpy(wordArray[cnt2 + 1].word, wordArray[cnt2].word);
				wordArray[cnt2 + 1].page = wordArray[cnt2].page;
			}
			strcpy(wordArray[cnt1].word, input_word);
			wordArray[cnt1].page = input_page;
			break;
		}
	}
}

int is_smaller(char *input_word, int input_page, int cnt)
{
	if(strcmp(input_word, wordArray[cnt].word) < 0)
		return 1;
	else if(strcmp(input_word, wordArray[cnt].word) == 0)
	{
		if(input_page < wordArray[cnt].page)
			return 1;
		else
			return 0;
	}
	else
		return 0;
}

void output(WORD *output_array)
{
	int		output_cnt = 0;
	char	last_print_word[30] = "";

	while(output_array[output_cnt].page != 0)
	{
		if(strcmp(last_print_word, "") == 0)
		{
			printf("%s\n", output_array[output_cnt].word);
			strcpy(last_print_word, output_array[output_cnt].word);
		}
		else if(strcmp(output_array[output_cnt].word, last_print_word) != 0)
		{
			printf("\n%s\n", output_array[output_cnt].word);
			strcpy(last_print_word, output_array[output_cnt].word);
		}
		else
		{
			printf(" ");
			
		}
		printf("%d", output_array[output_cnt].page);
		output_cnt++;
	}
	printf("\n");
}

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

int main(){
    int N;
    cin >> N;
    string s;
    ll ans = 0;
    map<string,int> Mp;
    for (int i = 0; i < N; i++)
    {
        cin >> s;
        sort(s.begin(),s.end());
        Mp[s]++;
    }
    for (auto p : Mp)
    {
        int sec = p.second;
        ans += (ll)sec*(sec-1)/2;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 11136
n = int(input())
ps = [int(p) for p in input().split()]

ls = [0 for _ in range(n)]
for i, p in enumerate(ps):
    ls[p-1] = i

cs = [ls[0]]
for i in range(1, n):
    cs.append(cs[-1] + ls[i])

xs = [c + 1 + i for i, c in enumerate(cs)]
ys = [cs[-1]+n+1] + [cs[-1] - c + 1 + n - i for i, c in zip(range(1, n), cs)]
print(" ".join(map(str, xs)))
print(" ".join(map(str, ys)))

Measured memory_bytes: 8880
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=i
 if l<H and A[i]<A[l]:g=l
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))


Measured memory_bytes: 65140
# coding: utf-8

# https://atcoder.jp/contests/abc092/tasks/arc093_a
# 16:37-16]53 done


def main():
    N = int(input())
    A = list(map(int, input().split()))

    S = [None] * N
    S[0] = abs(A[0])
    a = S[0]
    for i in range(1, N):
        a += abs(A[i]-A[i-1])
        S[i] = a

    print(S[N-1]-(abs(A[1]-A[0])+abs(A[0]))+abs(A[1])+abs(A[N-1]))

    for i in range(1, N-1):
        print(S[N-1]-(S[i+1]-S[i-1])+abs(A[i+1]-A[i-1])+abs(A[N-1]))

    print(S[N-2]+abs(A[N-2]))


main()


Measured memory_bytes: 14044
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i < (b); i++)
#define rrep(i, a, b) for (int i = a; i >= (b); i--)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
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;
}
void hr() {
   cerr << "--------------" << endl;
}
const int INF = 1001001001;
const int MOD = 1000000007;

vector<int> ans;
vector<int> to[100005], cost[100005];
void dfs(int u, int p = -1) {
   rep(i, 0, to[u].size()) {
      int v = to[u][i];
      int w = cost[u][i];
      if (v == p) continue;
      ans[v] = (ans[u] + w) % 2;
      dfs(v, u);
   }
}
int main() {
   cin.tie(0);
   ios_base::sync_with_stdio(0);

   int n;
   cin >> n;
   rep(i, 0, n - 1) {
      int a, b, w;
      cin >> a >> b >> w;
      a--, b--;
      to[a].push_back(b);
      cost[a].push_back(w);
      to[b].emplace_back(a);
      cost[b].push_back(w);
   }

   ans.resize(n);

   dfs(0);
   rep(i, 0, n) cout << ans[i] << endl;
   return 0;
}

Measured memory_bytes: 15232
// ALDS_1_1_D Maximum Profit

#include <iostream>
#define NMAX	200000
#define RMAX	1000000000

int main(int argc, char *argv[]){
	int N, R[NMAX];
	int diff_max = 1-RMAX;
	int R_min = RMAX;
	int diff;

	std::cin >> N;
	for(int i=0 ; i<N ; i++){
		std::cin >> R[i];
	}

	for(int i=0 ; i<N-1 ; i++){
		if(R_min > R[i]){
			R_min = R[i];
			for(int j=i+1 ; j<N ; j++){
				diff = R[j] - R[i];
				if(diff > diff_max){
					diff_max = diff;
				}
			}
		}
	}
	
	std::cout << diff_max << std::endl;

	return 0;
}



Measured memory_bytes: 3872
//"BISMILLAHIR RAHMANIR RAHIM"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
const long long M = 1e8 ;
int main()
{
    ll t;
    cin>>t;
   // while(t--)

    //
    ll n;
    if(t==1)
        n=0;
    else
        n=1;
    cout<<n;
    return 0;
}


Measured memory_bytes: 3596
#include<stdio.h>
#include<string.h>
#define it register int
#define ct const int
#define il inline
using namespace std;
typedef long long ll;
#define rll register ll
#define cll const ll
#define P 998244353
const int N=1005;
int a[N],pl[N],pr[N],K,n,mx,m,mk,p[N];
bool tag[N];
int main(){ 
	scanf("%d",&K);it i,j;
	for(i=1;i<=K;++i) scanf("%d",&a[i]),n+=a[i],mx=(a[i]>mx?a[i]:mx),pl[i]=K,pr[i]=i;
	for(i=1;i<=K;++i) if((a[i]<<1)<mx) return puts("-1"),0;
	for(i=1;i<=n;++i){
		for(j=1;j<=K;++j)
			if(!tag[j]){
				mx=0;it flag=1;
				for(it k=1;k<=K;++k) mx=(a[k]>mx?a[k]:mx);
				for(it k=1;k<=pl[j];++k) a[pr[k]]-=(!tag[pr[k]]);
				for(it k=1;k<=K;++k) if((a[k]<<1)+2<mx){flag=0;break;}
				if((a[j]<<1|1)<mx) flag=0;
				for(it k=1;k<=pl[j];++k) a[pr[k]]+=(!tag[pr[k]]);
				if(flag) break;
			}
		tag[j]=1,p[i]=j,--a[j],++m,mk=(mk>pl[j]?mk:pl[j]);
		if(i>=K&&(i==K||m==mk)){for(j=1;j<=K;++j) tag[j]=0,pl[p[i+j-K]]=j,pr[j]=p[i+j-K];m=mk=0;}
	} 
	for(i=1;i<=n;++i) printf("%d ",p[i]);puts("");
	return 0;
}

Measured memory_bytes: 1724
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)
function main()
    a,b=parseMap(split(readline()))
    println(ifelse(abs(a-b)%2==0,min(a,b)+div(abs(a-b),2),"IMPOSSIBLE"))
end
main()

Measured memory_bytes: 111408
N,M,Q = gets.split.map(&:to_i)
xs = (0..N).map{ (0..N).map{ 0 } }

M.times{
  l,r = gets.split.map(&:to_i)  
  xs[l][r] += 1
}

#p xs

ys = (0..N).map{ |i|
  row = [0]
  (1..N).each{ |j|
    row << (row[-1] + xs[i][j])
  }
  row
}

#p ys
zs = (0..N).map{ (0..N).map{ nil } }
Q.times { |a|
  p,q = gets.split.map(&:to_i)
  
  if !zs[p][q]
	zs[p][q] = (p..q).map{ |i| ys[i][q] }.inject(:+)
  end
  puts zs[p][q]
}

Measured memory_bytes: 13452
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <numeric>



int main()
{
	int a;

	std::cin >> a;

	std::cout << 48 - a << std::endl;

	return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int rn[][] = new int[17][17];
		
		int gx, gy;
		gx = scanner.nextInt();
		gy = scanner.nextInt();
		
		while(gx != 0 || gy != 0) {
			int n = scanner.nextInt();
			
			for(int x = 1; x <= gx; x++) {
				for(int y = 1; y <= gy; y++) {
					rn[x][y] = 0;
				}
			}
			
			for(int i = 0; i < n; i++) {
				int x = scanner.nextInt();
				int y = scanner.nextInt();
				rn[x][y] = -1;
			}
			
			for(int x = 1; x <= gx; x++) {
				if (rn[x][1] == -1) {
					for(int xx = x; xx <= gx; xx++) {
						rn[xx][1] = -1;
					}
					break;
				} else {
					rn[x][1] = 1;
				}
			}
			for(int y = 1; y <= gy; y++) {
				if(rn[1][y] == -1) {
					for(int yy = y; yy <= gy; yy++) {
						rn[1][yy] = -1;
					}
					break;
				} else {
					rn[1][y] = 1;
				}
			}
			
			for(int y = 2; y <= gy; y++) {
				for(int x = 2; x <= gx; x++) {
					if (rn[x][y] == -1) {
						continue;
					}

					int c = 0;
					if (rn[x - 1][y] != -1) {
						c += rn[x - 1][y];
					}
					if (rn[x][y - 1] != -1) {
						c += rn[x][y - 1];
					}
					rn[x][y] = c;
				}
			}
			
			System.out.println(rn[gx][gy]);
			
			gx = scanner.nextInt();
			gy = scanner.nextInt();
		}
	}
}

Measured memory_bytes: 25932
#include<bits/stdc++.h>
using namespace std;
const int INF=1e9+5;
int main()
{
int n,k;cin>>n>>k;
vector<int> h(n);
for(int &x : h)
scanf("%d",&x);
vector<int> dp(n,INF);
dp[0]=0;
for(int i=0;i<n;i++)
{
	for(int j=i+1;j<=i+k;j++)
	{
		dp[j]=min(dp[j],dp[i]+abs(h[j]-h[i]));
	}
}
printf("%d",dp[n-1]);
return 0;
}


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

int main() {
  int N;
  cin >> N;
  
  for (int i = 0; i < N; i++){
    string x;
    cin >> x;
    if (x == "Y"){
      cout << "Four" << endl;
      break;
    }
    else{
      if (i < N - 1){
      continue;
      }
      else{
      cout << "Three" << endl;
      }
    }
  }
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;

#define FOR(i,n) for (int (i) = 0; (i) < (n); i++)
//L~L+N-1

int A[200];

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

    int res = 0;
    for (int i = 0; i < N; i++) {
        A[i] = L + i;
    }
    
    int absmin = 1000000;
    for (int i = 0; i < N; i++) {
        res += A[i];
        if (abs(A[i]) < abs(absmin)) {
            res -= A[i];
            res += absmin;
            absmin = A[i];
        }
    }
    cout << res - 1000000 << "\n";

}

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

int main(){

    size_t n;
    std::cin >> n;

    std::vector<size_t> a(n);
    for(auto&& e : a){
        std::cin >> e;
    }

    std::vector<size_t> b(n);
    size_t index_begin = 0, index_end = n - 1;
    bool flag = true;
    for(long i = n - 1; i >= 0; i--){
        if(flag){
            b.at(index_begin) = a.at(i);
            index_begin++;
            flag = false;
        }else{
            b.at(index_end) = a.at(i);
            index_end--;
            flag = true;
        }
    }

    for(size_t i = 0; i < n; i++){
        if(i < n - 1){
            std::cout << b[i] << ' ';
        }else{
            std::cout << b[i] << std::endl;
        }
    }

    return 0;
}


Measured memory_bytes: 5248
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>

using namespace std;

int main(){

    double r;
    cin >> r;
    cout << fixed;
    cout << setprecision(15) << r*r*M_PI << endl;
    cout << setprecision(15) << 2*r*M_PI << endl;

    return 0;
}



Measured memory_bytes: 3300
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<numeric>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int CM = 130000;
char cn[CM + 10], * ci = cn + CM + 10, *owa = cn + CM, ct;
inline int getint() {
	if (ci - owa > 0) {
		memcpy(cn, owa, 10);
		ci -= CM;
		fread(cn + 10, 1, CM, stdin);
	}
	int A = 0;
	while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

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


	int X = getint(), Y = getint(), A = getint(), B = getint(), C = getint();

	int abc[400000];
	auto a = abc;
	auto b = abc + A;
	auto c = abc + A + B;

	rep(i, A + B + C) a[i] = getint();

	nth_element(a, b - X, b);
	nth_element(b, c - Y, c);
	if (X + Y > B) memcpy(b, b - X, (B - Y) * sizeof(int));
	else memcpy(c - X - Y, b - X, X * sizeof(int));
	nth_element(c - X - Y, c + C - X - Y, c + C);

	ll kotae = accumulate(c + C - X - Y, c + C, 0ll);
	//for (auto kari = c + C - X - Y; kari < c + C; kari++) kotae += *kari;
	printf("%lld", kotae);

	Would you please return 0;
}

Measured memory_bytes: 1408
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System.Threading.Tasks;

namespace AtCorder
{
	public class Program
	{
		static void Main(string[] args)
		{
			string s1 = Console.ReadLine();
			string s2 = Console.ReadLine();
			string s3 = Console.ReadLine();
			var c = new char[3];
			c[0] = s1[0];
			c[1] = s2[1];
			c[2] = s3[2];

			Console.WriteLine(new string(c));
		}
	}
}

Measured memory_bytes: 13140
N=int(input())
A = []
for i in range(N):
  A.append(int(input()))

left=[0]*(N+1)
right=[0]*(N+1)
for i in range(N):
  left[i+1]=max(left[i],A[i])
  right[N-1-i]=max(right[N-i],A[N-i-1])

ans=0
for i in range(N):
  ans=max(left[i],right[i+1])
  print(ans)

Measured memory_bytes: 20176
/**********************************************************
* @Author: 			   Kirito
* @Last Modified by:   Kirito
* @Remark:
**********************************************************/
#include <bits/stdc++.h>
#define lowbit(x) (x&(-x))
#define CSE(x,y) memset(x,y,sizeof(x))
#define INF 0x3f3f3f3f
#define Abs(x) (x>=0?x:(-x))
#define FAST ios::sync_with_stdio(false);cin.tie(0);
using namespace std;

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

const int maxn=111111;
const double pi = 3.141592653589;
const double mn = pi*2/60.0;
const double hn = pi*2/(12*60);

double h,m,a,b;

int main()
{
    cin>>a>>b>>h>>m;
    double k1 = m*mn;
    double k2 = (m+h*60)*hn;
    printf("%.9f\n",sqrt(a*a+b*b-2*a*b*cos(k1-k2)));
	return 0;
}


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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

template<typename H> bool chmin(H& v1, const H v2) { if (v1 > v2) { v1 = v2; return true; } return false; }
template<typename H> bool chmax(H& v1, const H v2) { if (v1 < v2) { v1 = v2; return true; } return false; }
template<typename H> void read(H& head) { cin >> head; }
template<typename H, typename ...T> void read(H& head, T& ...tail) { cin >> head; read(tail...); }
template<typename H> void write(H head) { cout << head << '\n'; }
template<typename H, typename ...T> void write(H head, T ...tail) { cout << head << " "; write(tail...); }
template<typename ...T> void die(T ...tok) { write(tok...); exit(0); }

const ll INF = 0x3f3f3f3f3f3f3f3fll;

vector<ll> v;
vector<vector<ll>> dp(3005, vector<ll>(3005, INF));

ll f(int x, int y, bool flag) {
	if (x > y) return 0;
	if (dp[x][y] != INF) return dp[x][y];

	if (flag) {
		dp[x][y] = max(f(x + 1, y, !flag) + v[x], f(x, y - 1, !flag) + v[y]);
	} else {
		dp[x][y] = min(f(x + 1, y, !flag) - v[x], f(x, y - 1, !flag) - v[y]);
	}

	return f(x, y, flag);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

	int n; read(n);
	v = vector<ll>(n);
	rep(i, 0, n) cin >> v[i];

	die(f(0, n - 1, 1));
}


Measured memory_bytes: 73216
import numpy as np

import math


n = int(input())


a = []


sum = 0


for i in range(n):
    a.append(np.array(list(map(int,input().split()))))

for i in range(n):
    for s in range(i,n):
        sum += np.linalg.norm(a[s] - a[i])


print(sum*2/n)


Measured memory_bytes: 18984
program main 
 implicit none
 integer*8 N,i,j,tmp
 read(*,*) N
 tmp = N - 1
 j = N/2
 do i=1,N/2
  if(mod(N,i)==0) then
   if(i-1+N/i-1 < tmp) then
    tmp = i-1+N/i-1
   end if
  end if
  j = min(j,N/i+1)
  if(j < i) exit
 end do
 write(*,*) tmp
end program main
  

Measured memory_bytes: 256
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws FileNotFoundException {

		//    	File file = new File("src/in.txt");
		//    	Scanner sc = new Scanner(file);

		Scanner sc = new Scanner(System.in);

		long N = sc.nextLong();
		long A = sc.nextLong();
		long B = sc.nextLong();

		if (A==0) {
			System.out.println("0");
		} else {
			long ans = A*(N/(A+B))+Math.min(A,N%(A+B));
			System.out.println(ans);
		}

	}
}

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

int main() {
	int h;
	cin >> h;
	int w;
	cin >> w;
	vector<string> a(h);
	for (int i = 0; i < h; i++) {
		cin >> a[i];
	}
 
	vector<bool> row(h, false);
	vector<bool> col(w, false);
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (a[i][j] == '#') {
				row[i] = true;
				col[j] = true;
			}
		}
	}
 
	for (int i = 0; i < h; i++) {
		if (row[i]) {
			for (int j = 0; j < w; j++) {
				if (col[j]) {
					cout << a[i][j];
				}
			}
			cout << endl;
		}
	}
}

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

// ll fuuu(ll n) {
//     if(n < 2) {
//         return 1;
//     } else {
//         return n * (n-2);
//     }
// }


int main() {
    ll n;
    cin >> n;
    ll a;
    if(n%2 == 1) {
        a = 0;
    } else {
        a = 0;
        ll i = 10;
        while(n/i > 0) {
            a += n/i;
            i *= 5;
        }
    }


    cout << a << endl;
}


Measured memory_bytes: 256
def dfs(a='', b='a'):
	if len(a) == N:
		print(a)
	else:
		i = 'a'
		while i < b:
			dfs(a + i, b)
			i = chr(ord(i) + 1)
		dfs(a + b, chr(ord(b) + 1))

N = int(input())
dfs()

Measured memory_bytes: 4404
d = {1:0, 2:0, 3:0, 4:0}
for i in range(3):
	a, b = list(map(int, input().split()))
	d[a] += 1
	d[b] += 1

if max(d.values()) <= 2:
	print("YES")
else:
	print("NO")



Measured memory_bytes: 2940
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;
typedef long long ll;

bool IsPrime(ll num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; 
    for (ll i = 3; i*i <= num+2; i += 2)
    {
        if (num % i == 0)
        {
            return false;
        }
    }
    return true;
}
/*
int main(){
  ll N;
  cin >> N;
  ll ans = 0;
  ll M = N;
  for(ll i=2;i*i<=N+10;i++){
    if(M%i==0 && IsPrime(i)){
      ll k=i;
      while (M%k==0){
        cout << k << endl;
	M/=k;
	k=k*i;
	ans++;
      }
    }
  }
  if(ans==0 && N>1) ans=1;
  cout << ans << endl;
}
*/

int main() {
  ll N;
  cin>>N;
  ll p=sqrt(N);
  vector<ll>a(p+10);
  for(ll i=0;i<p+10;i++) a[i]=0;
  ll n=N;
  ll ans=0;
  for(ll i=2;i<=p+10;i++){
    while(1){
      if(n%i==0)n/=i;
      else break;
      a[i]++;
    }
    if(n<i)break;
  }
  for(ll i=2;i<p+10;i++){
    if(a[i]!=0){
      for(ll u=1;;u++){
	if(a[i]>=u){
	  ans++;
	  a[i]-=u;
	}
	else break;
      }
    }
  }
  if(n!=1)ans++;
  if(N==1)cout<<0<<endl;
  else cout<<ans<<endl;
}


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

const ll INF = 1e18;
const ll MOD = 1000000007;
const ll MX = 1000001; //最大値

#define rep(i,n) for(ll i=0; i<(ll)(n); i++)
#define ALL(x) (x).begin(),(x).end()
#define MAX(x) *max_element(ALL(x))
#define PB push_back
#define F first
#define S second

vector<ll> b(MX), flag(MX);

int main() {
    int N; cin >> N;
    vector<ll> A(N);
    set<ll> s;
    rep(i, N) {
        cin >> A[i];
        b[A[i]]++;
        s.insert(A[i]);
    }

    for (int i : s) {
        for (int j = 2; j < MX; j++) {
            if (i * j >= MX) break;
            flag[i * j] = 1;
        }
    }
    int ans = 0;
    rep(i, N) {
        if (b[A[i]] == 1 && !flag[A[i]]) ans++; 
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 29732
//
//  main.cpp
//  A-un Breathing
//
//  Created by x15071xx on 2017/06/14.
//  Copyright ?? 2017??´ AIT. All rights reserved.
//

#include <iostream>

using namespace std;
int main(int argc, const char * argv[]) {
    
    int n;
    cin >> n;
    int count=0;
    for (int i = 0; i < n; i++) {
        
        string aun;
        
        cin >> aun;
        
        if (aun == "A") {
            count++;
        } else {
            count--;
            if (count < 0) {
                cout << "NO" << endl;
                return 0;
            }
        }
        
        
        
        
    }
    
    if (count == 0) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    
    
    
    return 0;
}

Measured memory_bytes: 3164
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using static System.Console;
using static System.Math;
using static AtCoder.Program;
 
namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            new ABC134().SolveC(new ConsoleInput(Console.In, ' '));
        }
    }
 
    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); } }
        public int ReadInt { get { return int.Parse(Read); } }
        public long ReadLong { get { return long.Parse(Read); } }
        public double ReadDouble { get { return double.Parse(Read); } }
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret; }
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret; }
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret; }
 
    }
  class ABC134
    {
        public void SolveC(ConsoleInput cin)
        {
            var n = cin.ReadInt;
            var a = new arrayC[n];
            for (int i = 0; i < n; i++)
            {
                a[i].Index = i;
                a[i].Value = cin.ReadInt;
            }
            var sortedA = a.OrderByDescending(x => x.Value).ToArray();
            for (int i = 0; i < n; i++)
            {
                if (sortedA[0].Index == i)
                {
                    WriteLine(sortedA[1].Value);
                }
                else
                {
                    WriteLine(sortedA[0].Value);
                }
            }
            ReadLine();
        }


        public struct arrayC
        {
            public int Index { get; set; }
            public int Value { get; set; }
        }
    }
}

Measured memory_bytes: 26680
#include<bits/stdc++.h>
#define rep1(i,n,a)    for(int i=0;i<n;i+=a)
#define rep2(i,n,a)    for(int i=a;i<n;i++)
#define rep3(n)        for(int i=0;i<n;i++)
#define inarr(arr,n)   rep1(i,n,1)cin>>arr[i]
#define ll             long long int
#define pb             push_back
#define all(v)         v.begin(),v.end()
#define trav(a,x)      for(auto x:a)
#define endl           "\n"
#define eb             emplace_back
#define fr             first
#define sc             second
#define gcd(a,b)       __gcd(a,b)
#define pres(a,x)      a.find(x)!=a.end()
#define sz(a)         (int)a.size()
#define pii            pair<int,int>
#define psi            pair<string,int>
#define pss            pair<string,string>
#define pll            pair<ll,ll>
#define vec            vector<int>
#define IOS            ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ret            return 0
#define pi             3.1415926536
#define hell           1000000007
#define narak          998244353
const int inf1=1e9;
const ll inf2=1e18;
const int N=100000;
using namespace std;
int dirs[4][2] ={{1,0},{-1,0},{0,1},{0,-1}};
// syntax for min priority_queue of pairs
// priority_queue<pair<ll,ll>,vector<pair<ll,int>>,greater<pair<ll,int>>> q;
int solve(){
 ll n,W;cin>>n>>W;
 ll w[n+1],v[n+1];
 rep3(n)cin>>w[i+1]>>v[i+1];
 ll dp[W+1][n+1];
 for(int i=0;i<=W;i++){
     for(int j=0;j<=n;j++){
         if(i==0 || j==0)dp[i][j]=0;
         else if(w[j]>i)dp[i][j]=dp[i][j-1];
         else{
             dp[i][j]=max(dp[i-w[j]][j-1]+v[j],dp[i][j-1]);
         }
     }
 }
 cout<<dp[W][n]<<endl;   
 ret;
}
int main(){
    IOS;
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int t=1;//cin>>t;
    while(t--){
        solve();
    }
    ret;
}
 

Measured memory_bytes: 79104
#include <iostream>
#include <stdio.h>
using namespace std;
int search(char str[]);
int main()
{
	char str[100];
	scanf("%s", str);
	printf("%d\n", search(str));
}

	int search(char str[])
	{
		int i;
		int num = 0;
		for (i = 0;i<100;i++) {
			if (str[i] == '1') {
				num++;
			}
		}
		return num;
	}

Measured memory_bytes: 256
# coding: utf-8;

def main():
    n = int(input())
    k = int(input())
    x = int(input())
    y = int(input())
    if n > k:
        print(k * x + (n - k) * y)
    else:
        print(n * x)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int main(){
	int n,a[200] ={};
	cin >> n;
	int ave = 0;
	for(int i =0; i <n; i++){
		cin >> a[i] ;
		ave += a[i];
	}
	ave /=n;

	int ans=0,ans2= 0;

	for(int i =0; i <n; i++){
		ans+=(a[i] -ave)*(a[i] -ave);
		ans2+=(a[i] -(ave+1))*(a[i] -(ave+1));
	}

	cout << min(ans,ans2) <<endl;
	
	return 0;
}

Measured memory_bytes: 256
A,B,C,D,E,F=map(int, input().split())

#A,B　水
#C,D satou
#E 溶解度　F 容量

V=0
node=0
total=0
sugar=0

for a in range(F//(100*A)+1):
    for b in range((F-100*A*a)//(100*B)+1):
        v=F-100*A*a-100*B*b
        for c in range(v//C+1):
            v2=v-c*C
            for d in range(v2//D+1):
                v3=v2-d*D
                if v3<0:
                    continue
                if a==0 and b==0:
                    continue
                if (c*C+d*D)/(a*A+b*B)>E:
                    continue
                nownode=100*(c*C+d*D)/(F-v3)
                if nownode>=node:
                    node=nownode
                    total=F-v3
                    sugar=(c*C+d*D)

print(total, sugar)


Measured memory_bytes: 3064
<?php
fscanf(STDIN, "%d", $n);
for ($i = 0; $i < $n; $i++) {
	fscanf(STDIN, "%d", $a[]);
}
$i = $c = 0;
while (!isset($f[$i])) {
	$c++;
	$f[$i] = 1;
	$i = $a[$i] - 1;
	if ($i == 1) exit("$c");
}
echo '-1';

Measured memory_bytes: 17140
#include<iostream>
#include <cstdio>
#include<cctype>
#include<string>

using namespace std;

int main(){
	int x;
	string s, s2, p;
	
	getline(cin,s);
	getline(cin,p);
	
	s2 = s + s;
	x = s2.find(p);
	
	if(x == -1) cout << "No" << endl;
	else		cout << "Yes" << endl;

	return 0;
}

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

long long vis[100005];
vector<long long> adj[100005];

void dfs(long long p)
{
    if(vis[p]==-1)
    {
        vis[p]=0;
        for(auto itr:adj[p])
        {
            dfs(itr);
            vis[p]=max(vis[itr]+1,vis[p]);
        }
    }
    else
    {
        return;
    }
}

int main()
{
    long long n,m;
    cin>>n>>m;
    for(int i=0;i<100005;i++)
{
    vis[i]=-1;
}
    for(int i=0;i<m;i++)
    {
        long long a,b;
        cin>>a>>b;
        adj[a].push_back(b);
    }
    long long max=0;
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==-1)
        {
            dfs(i);
            if(vis[i]>max)
            {
                max=vis[i];
            }
        }
    }
    cout<<max<<"\n";
    return 0;
}

Measured memory_bytes: 8576
#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
#define ALL(a)  (a).begin(),(a).end()
 
const ll mod = 1000000007;
const ll LINF = 1e13;
const ll LLINF = 1e18;
const ll ALPHABET = 26;
 
template <class T>
void Swap(T& r, T& l) {
  T tmp = r;
  r = l;
  l = tmp;
}
 
template<typename T>
istream& operator >> (istream& is, vector<T>& vec) {
  for (T& x : vec) is >> x; //for(int i=0; i<vec.size(); i++) is >> x[i]; とかでもいい
  return is;
}


int main(){
    // ll N,S,K;
    ll a,b;
    // cin >> a >>b >>c;
    
    cin >> a >> b;

    cout << max((ll)max(a+b,a-b),a*b);

}


Measured memory_bytes: 256
#include <iostream>
#include<algorithm>
#include<sstream>
#include<cmath>
#include<vector>
#include<iomanip>
#include<map>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i = 0; i < n;i++)
ll d[300][300],v, n, c, e, u, k, sum = 0,ans;
int main(void) {
	int n;cin >> n;
	int k = floor(sqrt(n));
	cout << k * k << endl;
}

Measured memory_bytes: 768
n = int(input())
X = [int(i) for i in input().split()]
Y = [int(j) for j in input().split()]
for p in [1,2,3]:
    D = (sum([abs(x-y)**p for (x,y) in zip(X,Y)]))**(1/p)
    print("{:.6f}".format(D))
D = max([abs(x-y) for (x,y) in zip(X,Y)])
print("{:.6f}".format(D))


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

#include <vector>
#define rep(i, n) for (int(i) = 0; (i) < (n); (i)++)
using namespace std;

int main() {
  float A, B, C, D;
  cin >> A >> B >> C >> D;
  if (ceil(C / B) <= ceil(A / D)) {
    cout << "Yes" << endl;

  } else {
    cout << "No" << endl;
  }
  //   cout << ceil(C / B) << ceil(A / D) << endl;
}

Measured memory_bytes: 3724