akhauriyash/Code-Regression huggingface dataset:
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define vvll vector<vll>
#define all(v) v.begin(),v.end()
#define itr(r,v) for(auto r=v.begin();r!=v.end();r++)
#define FOR(i,n) for(ll i=0;i<n;i++)
#define ffo(i,a,b) for(ll i=a;i<=b;i++)
#define rfr(i,a,b) for(ll i=a;i>=b;i--)
#define space cout<<"\n\n";
#define endl "\n"
#define pqmx priority_queue<ll>
#define pqmn priority_queue<ll,vll,greater<ll>>
#define fps(x,y) fixed<<setprecision(y)<<x
#define merg(a,b,c) set_union(a.begin(),a.end(),b.begin(),b.end(),inserter(c,c.begin()))
#define set_ar(arr,v) memset(arr,v,sizeof(arr))
#define ctime auto sttart = high_resolution_clock::now()
#define etime auto sttop = high_resolution_clock::now()
#define go_t ll testcases; cin>>testcases; for(ll caseno= 1 ;caseno <= testcases; caseno++)
#define ptime auto z1z = duration_cast<microseconds>(sttop-sttart); cout<<"\nTime taken : "<<z1z.count()<<" microseconds\n"
#define dbg1(x)             cout <<#x<<": "<<x<<'\n';
#define dbg2(x, y)          cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<'\n';
#define dbg3(x, y, z)       cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<'\n';
#define dbg4(a, b, c, d)    cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<'\n';
#define dbg5(a, b, c, d, e) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<<": "<<e<<'\n';

using namespace std;
using namespace std::chrono;

const ll MOD = 1e9 + 7;
const ll N = 1e5 + 5;
const ll maxN = 2e5 + 5;
const ll MAX_SIZE = 2e6 + 6;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const double PI = 3.14159265359;

ll powerM(ll x, ll y, ll M = MOD) { // default argument
	ll v = 1; x = x % M; while (y > 0) {if (y & 1)v = (v * x) % M; y = y >> 1; x = (x * x) % M;} return v;
}

ll power(ll x, ll y) {
	ll v = 1; while (y > 0) {if (y & 1)v = v * x; y = y >> 1; x = x * x;} return v;
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input1.txt", "r", stdin);
	freopen("output2.txt", "w", stdout);
#endif
	FIO
	ll n, W; cin >> n >> W;
	ll wt[n], val[n];
	ll max_val = 0;
	FOR(i, n) {
		cin >> wt[i] >> val[i];
		max_val += val[i];
	}
	ll dp[max_val + 1] = {};
	// dp[i] represents minimum weight that can be taken to form a value i
	FOR(i, max_val + 1) dp[i] = INF;
	dp[0] = 0;
	for (ll items = 0; items < n; items++) {
		for (ll i = max_val; i >= val[items] ; i--) {
			dp[i] = min(dp[i], wt[items] + dp[i - val[items]]);
		}
	}
	ll ans = INF;
	for (ll i = max_val; i >= 0; i--) {
		if (dp[i] <= W) {
			ans = i; break;
		}
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 4392
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func intMax(x, y int) int {
	return int(math.Max(float64(x), float64(y)))
}

func main() {
	sc.Split(bufio.ScanWords)

	N, C := scanInt(), scanInt()
	T := int(math.Pow10(5) * 2)

	table := make([][]int, C)
	for i := 0; i < C; i++ {
		table[i] = make([]int, T+1)
	}

	for i := 0; i < N; i++ {
		s, t, c := scanInt()*2-1, scanInt()*2, scanInt()-1
		for j := s; j <= t; j++ {
			table[c][j] = 1
		}
	}

	ans := 0
	for i := 0; i <= T; i++ {
		tmp := 0
		for j := 0; j < C; j++ {
			tmp += table[j][i]
		}
		ans = intMax(ans, tmp)
	}
	fmt.Println(ans)
}


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

int main() {
	int N; cin >> N;
	long long a[110000];
	for (int i = 0; i < N; i++) {
		cin >> a[i];
	}
	if (N == 1 && a[0] != 1) {
		cout << 1; return 0;
	}
	sort(a, a + N);
	a[N] = 0;
	long long ans = 0;
	for (int i = 1; i < N+1; i++) {
		long long sum = 1;
		while (a[i - 1] == a[i]&&i<N) {
			sum++;
			i++;
		}
		if (sum > a[i - 1]) {
			ans += sum - a[i-1];
		}
		else if(sum<a[i-1])ans += sum;
	}
	cout << ans;
}

Measured memory_bytes: 1024
#!/usr/bin/env python3
import sys
import numpy as np

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(H: int, N: int, A: "List[int]"):
    a = np.array(A)
    if a.sum()>=H:
        print(YES)
    else:
        print(NO)
    return


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

if __name__ == '__main__':
    main()


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

int main(){
    long int N,T;
    cin >>N>>T;
    long int t[N];
    
    for (int i=0;i<N;i++){
        cin >> t[i];}
        
        long int sum = T;
        
        for (long  int i=1;i<N;i++){
            if (t[i] < t[i-1] + T)
                sum = sum + (t[i]-t[i-1]);
            else
                    sum =sum + T;}
        
        cout << sum ;
    }

Measured memory_bytes: 1792
const MOD: usize = 998244353;
fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n: usize = sc.read();
    let m: usize = sc.read();
    let mut a: Vec<Vec<i64>> = (0..n)
        .map(|_| (0..m).map(|_| sc.read()).collect())
        .collect();

    let mut rank = 0;
    for col in 0..m {
        match (rank..n).find(|&i| a[i][col] == 1) {
            Some(row) => {
                a.swap(rank, row);
                assert_eq!(a[rank][col], 1);
                for i in 0..n {
                    if i == rank || a[i][col] != 1 {
                        continue;
                    }
                    for j in 0..m {
                        a[i][j] ^= a[rank][j];
                    }
                }
                rank += 1;
            }
            None => {}
        }
    }

    let mut pow2 = vec![0; n + m + 1];
    pow2[0] = 1;
    for i in 1..pow2.len() {
        pow2[i] = (pow2[i - 1] * 2) % MOD;
    }
    let ans = pow2[n + m - 1] + MOD - pow2[n + m - rank - 1];
    println!("{}", ans % MOD);

    // C(rank, x) * 2^(x-1) * 2^(m-x) * 2^(n-rank)
    // 2^(n+m-rank-1) * sum C(rank, x)
    // 2^(n+m-rank-1) * 2^rank - 2^(n+m-rank-1)
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


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

int top = 0; // 最後の要素の位置
int S[1000]; // Stackのデータ

// topにxを追加する
void push(int x){
  // topを加算してからSのその位置へ挿入
  top++;
  S[top] = x;
}

// topから要素を取り出す
int pop(){
  //topが指していた要素を返す
  int res = S[top];
  top--;
  return res;
}

int main(){
  // 読み込んだ1シンボル(オペランドや演算子)
  char s[100];
  // 計算する時に一時的に使う変数
  int a,b;

  // スペースまで読む．
  // sには12などのオペランドや+などの演算子が入る
  while(cin>>s){
    if(s[0] == '+'){
        a = pop();
        b = pop();
        push(a+b);
    }
    else if(s[0] == '-'){
        b = pop();
        a = pop();
        push(a-b);
    }
    else if(s[0] == '*'){
        a = pop();
        b = pop();
        push(a*b);
    }
    else{
      push(atoi(s));
    }
  }

  // 最後の1シンボルが計算結果になる
  cout << pop() << endl;
  return 0;
}



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

int main(){
    using namespace std;

    long long N; cin >> N;
    vector<long long> cusum(N+1, 0);

    for (int i = 1; i <= N; i++)
    {
        long long A; cin >> A;
        cusum[i] += cusum[i-1] + A;
    }

    map<long long, long long> m;
    for (int i = 0; i < N+1; i++) m[cusum[i]]++;
    long long cnt = 0;
    for(auto i : m){
        long long num = i.second;
        cnt += num * (num - 1) / 2;
    }
    cout << cnt << endl;
}


Measured memory_bytes: 14336
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <utility>

using namespace std;

int main()
{
    // ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	//freopen("input.in", "r", stdin);
	long long n, m;
	scanf("%lld %lld", &n, &m);
	if(n == 1 && m == 1) printf("1\n");
	else if(n == 1) printf("%lld\n", m-2);
	else if(m == 1) printf("%lld\n", n-2);
	else printf("%lld\n", (n-2)*(m-2));


}






Measured memory_bytes: 256
H, W = map(int, input().split())
A = [input() for i in range(H)]
B = []
for a in A:
    if not all([x == '.' for x in a]):
        B.append(a)
C = zip(*[b for b in zip(*B) if '#' in b])
for c in C:
    print(*c, sep='')


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

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;

int main(int argc, char** argv) 
{
#ifdef HOME
	if(IsDebuggerPresent())
	{
		freopen("../in.txt", "rb", stdin);
		freopen("../out.txt", "wb", stdout);
	}
#endif
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.precision(10);
	cout << fixed;
	int N;
	cin >> N;
	int64_t res = 0;
	for (int A = 1; A < N; ++A)
	{
		for (int B = 1; A*B < N; ++B)
			res++;
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 3608
#include<stdio.h>
#include<string.h>
  
#define M 1046527
#define L 14
  
char H[M][L]; /* Hash Table */
  
int getChar(char ch){
  if ( ch == 'A') return 1;
  else if ( ch == 'C') return 2;
  else if ( ch == 'G') return 3;
  else if ( ch == 'T') return 4;
}
  
/* convert a string into an integer value */
long long getKey(char str[]){
  long long sum = 0, p = 1, i;
  for ( i = 0; i < strlen(str); i++ ){
    sum += p*(getChar(str[i]));
    p *= 5;
  }
  return sum;
}
  
int h1(int key){ return key%M; }
int h2(int key){ return 1+(key%(M-1)); }
  
int find(char str[]){
  long long key,i,h;
  key=getKey(str);
  for(i=0;;i++){
    h=(h1(key)+i*h2(key))%M;
    if(strcmp(H[h],str)==0)return 1;
    else if(strlen(H[h])==0)return 0;
  }
  return 0;
}
     
  
int insert(char str[]){
  long long key,i,h;
  key=getKey(str);
  for(i=0;;i++){
    h=(h1(key)+i*h2(key))%M;
    if(strcmp(H[h],str)==0)return 1;
    else if(strlen(H[h])==0){
      strcpy(H[h],str);
      return 0;
    }
  }
  return 0;
  
}
  
int main(){
    int i, n, h;
    char str[L], com[9];
    for ( i = 0; i < M; i++ ) H[i][0] = '\0';
      
    scanf("%d", &n);
      
    for ( i = 0; i < n; i++ ){
    scanf("%s %s", com, str);
      
    if ( com[0] == 'i' ){
        insert(str);
    } else {
        if (find(str)){
        printf("yes\n");
        } else {
        printf("no\n");
        }
    }
    }
  
    return 0;
}

Measured memory_bytes: 16024
import sys;input=sys.stdin.readline
X, Y, Z, A, B = map(int, input().split())
P = sorted(list(map(int, input().split())))[::-1][:X]
Q = sorted(list(map(int, input().split())))[::-1][:Y]
R = sorted(list(map(int, input().split())))
PQ = sorted(P+Q)[::-1]

c = 0
while R and PQ:
    x = PQ[-1]
    y = R[-1]
    if x < y:
        PQ.pop()
        c += R.pop()
        continue
    break
print(sum(PQ)+c)


Measured memory_bytes: 93420
n, m, l = map(int, input().split())

A = [[0 for i in range(m)] for j in range(n)]
B = [[0 for i in range(l)] for j in range(m)]
C = [[0 for i in range(l)] for j in range(n)]

for i in range(n):
    v = list(map(int, input().split()))
    for j in range(m):
        A[i][j] = v[j]
for i in range(m):
    v = list(map(int, input().split()))
    for j in range(l):
        B[i][j] = v[j]

for i in range(l):
    for j in range(n):
        for k in range(m):
            C[j][i] += A[j][k] * B[k][i]

for i in range(n):
    for j in range(l - 1):
        print(C[i][j], "", end = "")
    print(C[i][l - 1])



Measured memory_bytes: 7152
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<vector>
#include<climits>
#include<map>
#include<string>
#include<functional>
#include<iomanip>
#include<deque>
#include<random>

using namespace std;
typedef long long ll;
typedef double lldo;
#define mp make_pair
#define pub push_back
ll gcd(ll a, ll b) { if (a % b == 0) { return b; } else  return gcd(b, a % b); }
ll lcm(ll a, ll b) { if (a == 0) { return b; }return a / gcd(a, b) * b; }
template<class T>ll LBI(vector<T>& ar, T in) { return lower_bound(ar.begin(), ar.end(), in) - ar.begin(); }
template<class T>ll UBI(vector<T>& ar, T in) { return upper_bound(ar.begin(), ar.end(), in) - ar.begin(); }

string S;
ll dp[200001][3] = {};

int main() {
	cin >> S;
	dp[1][1] = 1;
	dp[1][2] = 0;
	for (int i = 2; i <= S.length(); i++) {
		if (S[i - 2] != S[i - 1])dp[i][1] = dp[i - 1][1] + 1;
		dp[i][1] = max(dp[i][1], dp[i - 1][2] + 1);
		dp[i][2] = dp[i - 2][1] + 1;
		if (i == 2) {
			dp[2][2] = 1;
		}
		else if (i == 3) {
			dp[3][2] = 2;
		}
		else {
			if (S[i - 1] != S[i - 3] && S[i - 2] != S[i - 4])dp[i][2] = max(dp[i][2], dp[i - 2][2] + 1);
		}
	}
	cout << max(dp[S.length()][1], dp[S.length()][2]) << endl;
	return 0;
}

Measured memory_bytes: 5252
#include<stdio.h>
#include<string>
#include<iostream>
#include<vector>

using namespace std;

int main(void)
{
    int px,nx;
    int r,D;

    scanf("%d %d %d",&r,&D,&nx);    
    for(int i=0;i<10;i++)
    {
        px = nx;
        nx = r*nx - D;
        printf("%d\n",nx);
    }

    return 0;
}

Measured memory_bytes: 256
N = int(input())
S = input()
ans = True
if N%2==1:
    print('No')
else:
    for i in range(N//2):
        if S[i]==S[i+N//2]:
            continue
        else:
            ans = False
            break
    if ans:
        print('Yes')
    else:
        print('No')

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

#define LL long long
#define LD long double
#define Mod 1000000007
#define L_Mod 17100000013

const double eps = 1e-9;
const int INF = 0x3f3f3f3f;
const double PI = 3.1415926535;

#define NO_TLE std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define ree(a,n) memset(a,n,sizeof(a));

#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define red(i,l,u) for(int (i)=(int)(l);(i)>=(int)(u);--(i))

set<int> st;

int main()
{
    int x,n,ans=0;
    cin >> n;
    while(n--)
    {
        cin>>x;
        st.insert(x);
        auto it=st.begin();
        if(x==(*it))ans++;
    }
    cout<<ans<<endl;
    return 0;
}
























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

using namespace std;

#define int long long 
#define double long double 
#define endl '\n'
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define SIZE 10000005

int32_t main()
{
	int x1,x2,x3,x4,x5;
	
	cin >> x1 >> x2 >> x3 >> x4 >> x5;
	if(x1 == 0) cout << 1 << endl;
	else if(x2 == 0) cout << 2 << endl;
	else if(x3 == 0) cout << 3 << endl;
	else if(x4 == 0) cout << 4 << endl;
	else cout << 5 << endl;
	return 0;
}


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

// types
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;

// macros
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int mod = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

ll cost(ll ave, vector<ll> v){
  ll sum = 0;
  REP(i, v.size())
    sum += (ll)pow(v[i]-ave, 2);
  
  return sum;
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  ll n;
  cin >> n;
  
  vector<ll> a(n);
  REP(i, n)
    cin >> a[i];
  
  ll sum = accumulate(a.begin(), a.end(), 0LL);
  cout << min(cost(sum/n, a), cost(sum/n+1, a)) << endl;
      
  
}

Measured memory_bytes: 256
from collections import deque

n = int(input())
Tree_dict = {}
for _ in range(n-1):
    a, b = map(int, input().split())
    if a in Tree_dict.keys():
        Tree_dict[a].append(b)
    else:
        Tree_dict.update({a:[b]})
    if b in Tree_dict.keys():
        Tree_dict[b].append(a)
    else:
        Tree_dict.update({b:[a]})

deque = deque()
deque.append(1)

Visited_one = [-1 for _ in range(n+1)]
Visited_one[1] = 0

while deque:
    node = deque.popleft()
    next_nodes = Tree_dict[node]
    for next_node in next_nodes:
        if Visited_one[next_node] != -1:
            continue
        else:
            Visited_one[next_node] = Visited_one[node] + 1
            deque.append(next_node)


deque.append(n)

Visited_n = [-1 for _ in range(n+1)]
Visited_n[n] = 0

while deque:
    node = deque.popleft()
    next_nodes = Tree_dict[node]
    for next_node in next_nodes:
        if Visited_n[next_node] != -1:
            continue
        else:
            Visited_n[next_node] = Visited_n[node] + 1
            deque.append(next_node)

# print(Visited_one)
# print(Visited_n)

fen = 0
snu = 0

for i in range(1,n+1):
    if Visited_n[i] >= Visited_one[i]:
        fen += 1
    else:
        snu += 1

if fen > snu:
    ans = 'Fennec'
else:
    ans = 'Snuke'
print(ans)

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
int A[101010],B[101010],C[101010],D[101010];
map<pair<int,int>,vector<int>> M;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i]>>B[i];
		M[{A[i],B[i]}].push_back(i);
	}
	
	FOR(i,N) {
		if(i==0) {
			if(A[i]) return _P("-1\n");
		}
		else {
			C[i]=1;
			if(M.count({A[i]-1,B[i]-1})+M.count({A[i]-1,B[i]})+M.count({A[i]-1,B[i]+1})==0) return _P("-1\n");
		}
		if(i==1) {
			if(B[i]) return _P("-1\n");
		}
		else {
			D[i]=1;
			if(M.count({A[i]-1,B[i]-1})+M.count({A[i],B[i]-1})+M.count({A[i]+1,B[i]-1})==0) return _P("-1\n");
		}
	}
	
	int ret=2*N-2;
	FORR(m,M) {
		auto a=m.first;
		a.first++;
		a.second--;
		y=0;
		FORR(x,m.second) {
			if(C[x]&&D[x]&&M.count({A[x]-1,B[x]-1})) {
				ret--;
				C[x]=D[x]=0;
			}
			if(D[x]&&M.count(a)&&y<M[a].size()) {
				C[M[a][y]]=0;
				ret--;
				y++;
			}
			
		}
	}
	cout<<ret<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 12800
package main

import (
	"bufio"
	f "fmt"
	"os"
	"sort"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	sc.Scan()
	a, err := strconv.Atoi(sc.Text())
	if err != nil {
		f.Println(err)
	}
	return a
}

func scanSlice(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = scanInt()
	}
	return a
}

func main() {

	sc.Split(bufio.ScanWords)

	var n, k int
	f.Scan(&n, &k)

	hp := scanSlice(n)
	sort.Ints(hp)

	flag := 0
	atack := 0

	if k >= n {
		f.Println(0)
	} else {
		for i := 0; i < n; i++ {
			flag++
			if flag > k {
				atack += hp[n-1-i]
			}
		}
		f.Println(atack)
	}

}


Measured memory_bytes: 4736
import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        long n = sc.nextLong();
        long[] a = new long[5];
        for (int i = 0; i < 5; i++) {
            long x = sc.nextLong();
            a[i] = n / x;
            if (n % x != 0) {
                a[i]++;
            }
        }
        Arrays.sort(a);
        long ans = 5 + a[4] - 1;
        System.out.println(ans);
    }
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() {
        if (hasNextByte())
            return buffer[ptr++];
        else
            return -1;
    }
    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }
    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
        return hasNextByte();
    }
    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext())
            throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
            throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() {
        return Double.parseDouble(next());
    }
}


Measured memory_bytes: 21460
# import numpy as np
# import scipy as sp
# print(a,b,c,sep="") # 半角スペースなしで出力(abc)
# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(str,list(input()))) for i in range(h)]  # 文字列の二次元配列入力
# s = [list(map(int, input().split())) for i in range(n)] # 数値の二次元配列入力
# a = b[:], a = [x[:] for x in b] # deepcopy
# chr(ord('a') + 1) # chrのインクリメント
# s.sort(key=lambda x: x[1], reverse=False) # 2番目の要素で昇順にソート（Trueなら降順）
#

a, b, x = map(int, input().split())
if a+b >= x and a <= x:
    print('YES')
else:
    print('NO')


Measured memory_bytes: 38256
#include<stdio.h>
#define MAX 100000

int A[MAX],n;

int partition(int p,int r){
    int x,i,j,t;
    x = A[r];
    i = p - 1;
    for(j = p;j < r;j++){
       if(A[j] <= x){
           i++;
           t = A[i];
           A[i] = A[j];
           A[j] = t;
       } 
    }
    t = A[i + 1];
    A[i + 1] = A[r];
    A[r] = t;
    return i + 1;

}

int main(){
    int i,q;

    scanf("%d",&n);
    for(i = 0;i < n;i++)
    scanf("%d",&A[i]);
    q = partition(0,n-1);

    for(i = 0;i < n;i++){
        if(i) printf(" ");
        if(i == q) printf("[");
        printf("%d",A[i]);
        if(i == q) printf("]");
    }
    printf("\n");

    return 0;
}


Measured memory_bytes: 2120
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.next();
        System.out.println( solve(S) );
    }

    private static String solve(String S) {
        if( S.length() == 26 ) {
            return solve26(S);
        } else {
            return solve25(S);
        }
    }

    private static String solve26(String S) {
        for (int i = S.length() - 1; i >= 0; i--) {
            Set<Character> used = usedChars(S, i);
            for (char c = (char)(S.charAt(i) + 1); c <= 'z' ; c++) {
                if( !used.contains(c) ) {
                    return S.substring(0, i) + c;
                }
            }
        }
        return "-1";
    }

    private static Set<Character> usedChars(String S, int to) {
        Set<Character> used = new HashSet<>();
        for (int i = 0; i < to; i++) {
            used.add( S.charAt(i) );
        }
        return used;
    }

    private static String solve25(String S) {
        Set<Character> used = new HashSet<>();
        for (int i = 0; i < S.length(); i++) {
            used.add( S.charAt(i) );
        }

        for (int i = 0; i < 26; i++) {
            char c = (char)('a' + i);

            if( !used.contains(c) ) {
                return S + c;
            }
        }

        throw new RuntimeException("wtf");
    }
}

Measured memory_bytes: 21844
#include<string>
#include<iostream>
#include<algorithm>
#include<set>
#include<math.h>
#include<vector>
#include<sstream>
#include<queue>
#include<functional>
#include<bitset>
#include<cstdio>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include <string.h>
using ll = long long;
 
#define rep(i, n) for(ll i = 0; i < (int)(n); i++)
#define reps(i,x) for(ll i=1;i<=(int)(x);i++)
#define rrep(i,x) for(ll i=((int)(x)-1);i>=0;i--)
#define rreps(i,x) for(ll i=(int)(x);i>0;i--)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define vll vector<ll>
#define vi vector<int>
#define mp make_pair
#define vpll vector<pair<ll,ll>>
#define vpi vector<pair<int,int>>
#define mod 1000000007 
using namespace std;
int a[200000];
int main() {
  ll sum = 0, n;
  cin >> n;
  rep(i, n){
    cin >> a[i];
    a[i] = a[i] -i -1;
  }
  sort(a, a+n);
  int id=round(n*1.0/2)-1;
  int md = a[id];
  rep(i,n)
    sum += abs(a[i]-md);
  cout <<sum<< endl;
}


Measured memory_bytes: 1024
#include <string>
#include <vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<functional>
#include<list>
#include<deque>
#include<bitset>
#include<set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<sstream>
#include<complex>
#include<iomanip>
#include<numeric>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))
#define peat(X,Y) for (;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T> using vv=vector<vector<T>>;
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"<<endl; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
const ll MOD=1e9+7;

int main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);
  string str;
  cin>>str;
  int n=str.size();
  rep(i,n){
    if(i+1<n && str[i]==str[i+1]){
      cout<<i+1<<" "<<i+2<<endl;
      return 0;
    }
    if(i+2<n && str[i]==str[i+2]){
      cout<<i+1<<" "<<i+3<<endl;
      return 0;
    }
  }
  cout<<"-1 -1"<<endl;
  return 0;
}


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

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

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<Int> a(n);
  for(Int i=0;i<n;i++) cin>>a[i];
  sort(a.begin(),a.end());

  vector<Int> ans(n);

  Int m=0;
  map<Int, Int> r;

  vector<vector<Int> > G(n);
  for(Int i=0;i<n;i++){
    auto x=factorize(a[i]);
    for(auto p:x){
      if(!r.count(p.first)) r[p.first]=m++,G.emplace_back();
      G[i].emplace_back(n+r[p.first]);
      G[n+r[p.first]].emplace_back(i);
    }
  }
  
  vector<Int> used(n+m,0),post(n,0);
  for(Int t=0;t<n;t++){
    vector<Int> cs(n+m,-1);
    Int color=0;
    for(Int i=0;i<n+m;i++){
      if(used[i]||~cs[i]) continue;
      queue<Int> q;
      cs[i]=color;
      q.emplace(i);
      while(!q.empty()){
	Int v=q.front();q.pop();
	for(Int u:G[v]){
	  if(used[u]||~cs[u]) continue;
	  cs[u]=color;
	  q.emplace(u);
	}
      }
      color++;
    }
    
    Int idx=-1;
    for(Int i=0;i<n;i++){
      if(used[i]||post[i]) continue;
      idx=i;
      break;
    }
    
    used[idx]=1;
    ans[t]=idx;
    
    for(Int i=0;i<n;i++){
      if(cs[idx]!=cs[i]) continue;
      post[i]=__gcd(a[idx],a[i])<=1;
    }
  }

  vector<Int> b(n);
  for(Int i=0;i<n;i++) b[i]=a[ans[i]];
  
  vector<vector<Int> > H(n);
  for(Int i=0;i<n;i++)
    for(Int j=i+1;j<n;j++)
      if(__gcd(b[i],b[j])>1) H[i].emplace_back(j);

  vector<Int> indeg(n);
  for(Int i=0;i<n;i++)
    for(Int j:H[i]) indeg[j]++;
  
  using P = pair<Int, Int>;
  priority_queue<P> pq;
  for(Int i=0;i<n;i++)
    if(!indeg[i]) pq.emplace(b[i],i);

  vector<Int> c;
  while(!pq.empty()){
    P p=pq.top();pq.pop();
    c.emplace_back(p.first);
    for(Int u:H[p.second]){
      indeg[u]--;
      if(!indeg[u]) pq.emplace(b[u],u);
    }
  }
  
  for(Int i=0;i<n;i++){
    if(i) cout<<" ";
    cout<<c[i];
  }
  cout<<endl;
  return 0;
}


Measured memory_bytes: 14464
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define range(i,a,n) for(int i=(a);i<(n);i++)

#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

int dx[]={1,0,-1,0,1,-1,-1,1},dy[]={0,1,0,-1,1,1,-1,-1};

template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S acm(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}

ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	vector<pii> ans;
	if(n%2==0){
		range(i,1,n+1){
			range(j,i+1,n+1){
				if(j==i||j==n+1-i)continue;
				ans.push_back(pii(i,j));
			}
		}
	}
	else{
		range(i,1,n){
			range(j,i+1,n){
				if(j==i||j==n-i)continue;
				ans.push_back(pii(i,j));
			}
		}
		range(i,1,n)ans.push_back(pii(n,i));
	}
	cout<<ans.size()<<endl;
	rep(i,ans.size()){
		cout<<ans[i].fs<<" "<<ans[i].sc<<endl;
	}
}

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

bool func(int data1,int data2,int data3){
    int a[3];
    a[0] = data1;a[1]=data2;a[2]=data3;
    sort(a,a+3);
    if(data1 == a[1]){
        return true;
    }else{
        return false;
    }
}

int main(void){
    int n;
    cin >> n;

    vector<int> data = vector<int>(n);

    for(int i=0;i<n;i++){
        cin >> data[i];
    }
    int count = 0;
    for(int i=1;i<n-1;i++){
        if(func(data[i],data[i-1],data[i+1])){
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
/*
 KUNAL RAUT (ZUKONIT14)  :- "DO WHAT YOU LIKE!"
 -PICT,PUNE! :)
 */
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define ld long double
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mod 1000000007
#define mod9 1000000009
#define pi 3.1415926535
#define MAXN 1000001
#define N 1000001
#define MAX2N 1*1000 + 10
#define all(v) v.begin(), v.end()
#define ms(s, n) memset(s, n, sizeof(s))
#define prec(n) fixed<<setprecision(n)
#define forci(p,n) for(ll i=p;i<(ll)n;i++)
#define forcj(p,n) for(ll j=p;j<(ll)n;j++)
#define bolt ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define bits(a) __builtin_popcount(a)
#define test ll t;cin>>t;for(ll testi=0;testi<t;testi++)
ll zero=0;
ll one=1;
ll gcd(ll a,ll b){    if(b==0) return a;    return gcd(b,a%b);}
ll lcm(ll a,ll b) {    return (a/gcd(a,b)*b);}
ll expo(ll x, ll y) {ll res=1;x=x%mod;while(y>0){if(y&1)res=(1ll*res*x)%mod;
    y=y>>1;x=(1ll*x*x)%mod;} return res;}
ll ncr(ll n,ll r){ ll res=1; if(r>n-r)r=n-r; for(ll i=0;i<r;i++) {  res*=n-i;  res/=i+1; } return res;}
ll max(ll a,ll b){return (a>b)?a:b;}
bool prime(ll n){ll i;for(i=2;i<=sqrt(n);i++){if(n%i==0)return false;}return true;}
bool sortbysec(const pair<ll,ll> &a,const pair<ll,ll> &b)
{   if(a.second == b.second)
    return a.first < b.first;
    return (a.second < b.second);}
//https://www.youtube.com/watch?v=WTJSt4wP2ME

ll rr[]={0,1,1,1,0,-1,-1,-1,};
ll cc[]={1,1,0,-1,-1,-1,0,1};

signed main()
{
    bolt;
    ll a,b,c;cin>>a>>b>>c;
    if((a==b && a!=c) || (a==c && a!=b) || (c==b && a!=c))
        cout<<"Yes";
    else
        cout<<"No";
        
}


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

class D
{
	static void Main()
	{
		Func<int[]> read = () => Console.ReadLine().Split().Select(int.Parse).ToArray();
		var h = read();
		var n = h[0];
		var p = read();
		var map = new int[n + 1].Select(_ => new List<int>()).ToArray();
		foreach (var r in new int[h[1]].Select(_ => read()))
		{
			map[r[0]].Add(r[1]);
			map[r[1]].Add(r[0]);
		}

		var c = 0;
		var used = new bool[n + 1];
		var q = new Queue<int>();
		var s = new HashSet<int>();

		for (int i = 1; i <= n; i++)
		{
			if (used[i]) continue;
			used[i] = true;
			q.Enqueue(i);
			s.Add(i);

			while (q.Any())
				foreach (var np in map[q.Dequeue()])
				{
					if (used[np]) continue;
					used[np] = true;
					q.Enqueue(np);
					s.Add(np);
				}
			c += s.Select(x => p[x - 1]).Count(s.Contains);
			s.Clear();
		}
		Console.WriteLine(c);
	}
}


Measured memory_bytes: 36768
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
using namespace std;
using ll = int64_t;
using vi = vector<int>;
using vvi = vector<vi>;

int main() {
    string s;
    cin >> s;
    int n = s.size();

    int an = -2, se = -2;

    rep(i, n) {
        if(i != n-1 && s[i] == s[i+1]) {
            an = i;
            se = i+1;
            break;
        }
        if(i < n-2 && s[i] == s[i+2]) {
            an = i;
            se = i+2;
            break;
        }
    }

    cout << an+1 << ' ' << se+1 << endl;
}

Measured memory_bytes: 512
n,a,b = map(int,input().split())

p = b-a-1

if p%2==0:
    ans=0
    if a <=n-b:
        k = a-1
        a-=k
        b-=(k+1)
        ans+=k+1
    else:
        k = n-b
        a+=(k+1)
        b+=k
        ans += k+1
    p=b-a-1

    print(ans + (p+1)//2)
else:
    print((p+1)//2)

Measured memory_bytes: 9204
#include <bits/stdc++.h>
#define dum(x) cout<<#x<<'='<<x<<endl
using namespace std;

int main() {
  int a, b, c, d, e;
  cin >> a >> b >> c >> d >> e;
  int ans;
  if (a <= 0) {
    ans = abs(a) * c;
    ans += d;
    ans += b * e;
  } else {
    ans = (b - a) * e;
  }
  cout << ans << endl;
}



Measured memory_bytes: 3104
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush, heapify
import math
import itertools
import random
 
# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
INF = float('inf')
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    X = inputInt()
    
    ans = 0
    total = 0
    for i in range(1,X+1):
        total += i
        if total >= X:
            ans = i
            break
            
    print(ans)
    
    
if __name__ == "__main__":
	main()


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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;
const int mod = 1e9 + 7;

bool checked[1000010];

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());

    int res = 0;
    for (int i = 0; i < n; ++i) {
        if (i < n - 1){
            if (a[i] == a[i+1]){
                checked[a[i]] = true;
                continue;
            }
        }
        if (!checked[a[i]]){
            res++;
        }
        for (int j = a[i]; j < 1000010; j += a[i]) {
            checked[j] = true;
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 5032
import java.util.Scanner;

public class Main{
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		long a = sc.nextLong();
		String op = sc.next();
		long b = sc.nextLong();
		
		switch(op){
			case "+":
				System.out.println((long)(a + b));
				break;
			case "-":
				System.out.println((long)(a - b));
		}
		sc.close();
	}
}


Measured memory_bytes: 10192
#include <bits/stdc++.h>
#define int long long
using namespace std;
 
const int N = 1e5 + 5;

struct edge_list {
	int u, v, w;
	bool operator < (const edge_list &o) const {
		return w < o.w;
	}
};

int n, m, k, mst_cost = 0, up[N << 1], c[N];
bool visited[N];
edge_list edge[N];

int union_find(int u) {
	if(up[u] == u) {
		return u;
	} else {
		return up[u] = union_find(up[u]);
	}
}

void union_merge(int u, int v) {
	up[union_find(u)] = union_find(v);
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m >> k;
	for(int i = 1; i <= n; ++i) {
		cin >> c[i];
		visited[c[i]] = 1;
	}
	for(int i = 1, u, v, w; i <= m; ++i) {
		cin >> u >> v >> w;
		if(!c[u]) u += k;
		else u = c[u];
		if(!c[v]) v += k;
		else v = c[v];
		edge[i] = {u, v, w};
	}
	for(int i = 1; i <= n + k; ++i) {
		up[i] = i;
	}
	int cnt = 0;
	sort(edge + 1, edge + m + 1);
	for(int i = 1; i <= m; i++) {
		if(cnt == k - 1) break;
		if(union_find(edge[i].u) != union_find(edge[i].v)) {
			union_merge(edge[i].u, edge[i].v);
			mst_cost += edge[i].w;
			cnt++;
		}
	}
	if(cnt == k - 1) cout << mst_cost;
	else cout << -1;
}

Measured memory_bytes: 4992
using System;

class ITP1_7_D{
    public static void Main(){
            int n, m, l;
            long[,] matrixA, matrixB, matrixC;
            string[] Input;

            Input = Console.ReadLine().Split(' ');
            n = int.Parse(Input[0]);
            m = int.Parse(Input[1]);
            l = int.Parse(Input[2]);

            matrixA = new long[n, m];
            matrixB = new long[m, l];
            matrixC = new long[n, l];

            for(int i = 0; i < n; i++){
                Input = Console.ReadLine().Split(' ');
                for(int j = 0; j < m; j++)
                    matrixA[i, j] = long.Parse(Input[j]);
            }
            for(int i = 0; i < m; i++){
                Input = Console.ReadLine().Split(' ');
                for(int j = 0; j < l; j++)
                    matrixB[i, j] = long.Parse(Input[j]);
            }

            for(int i = 0; i < n; i++){
                for(int j = 0; j < l; j++){
                    matrixC[i, j] = 0;
                    for(int k = 0; k < m; k++)
                        matrixC[i, j] += matrixA[i, k] * matrixB[k, j];
                }
            }
            
            for(int i = 0; i < n; i++){
                for(int j = 0; j < l; j++){
                    if(j != 0) Console.Write(" ");
                    Console.Write(matrixC[i, j]);
                }
                Console.WriteLine();
            }
    }
}

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

using namespace std;

int main(){
	int n,m,res = 0;
	cin >> n >> m;
	vector<vector <bool>> g;
	vector<int> k;
	g.resize(n);
	k.resize(n);
	for(int i=0;i<n;++i){
		g[i].resize(n);
		k[i] = i;
		for(int j=0;j<n;++j){
			g[i][j] = false;
		}
	}
	for(int i=0;i<m;++i){
		int from,to;
		cin >> from >> to;
		g[from-1][to-1] = 1;
		g[to-1][from-1] = 1;
	}
	do{
		bool flag = true;
		if(k[0]!=0)break;
		for(int i=1;i<n;++i){
			int from = k[i-1],to = k[i];
			if(!g[from][to]){
				flag = false;
				break;
			}
		}
		if(flag)res++;
	}while(next_permutation(k.begin(),k.end()));
	cout << res << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)) {
			int a = sc.nextInt();

			if (a == 1) {
				System.out.println(1);
				return;
			}
			int result = 0;
			int max = 0;
			for (int i = 1; i <= a; i++) {
				int tmp = i;
				for (int j = 1; j < 8; j++) {
					if (tmp % 2 == 0) {
						tmp /= 2;
					} else {
						if (max < j - 1) {
							result = i;
							max = j - 1;
						}
						break;
					}
				}
			}
			System.out.println(result);
		}
	}
}


Measured memory_bytes: 21972
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int h,w,m;
    cin>>h>>w>>m;
    pair<int,int> x[m];
    map<int, int> fx,fy;
    map<pair<int,int>,int> p;
    for(int i=0;i<m;i++)
    {
      cin>>x[i].first>>x[i].second;
      fy[x[i].second]++;
      fx[x[i].first]++;
      p[x[i]]=1;
    }
    int mx=0,my=0;
    vector<int> vx,vy;
    for(auto i:fx)
    {
        if(i.second>mx)
            mx=i.second;
    }
    for(auto i:fy)
    {
        if(i.second>my)
            my=i.second;
    }
    for(auto i:fx)
    {
        if(i.second==mx)
            vx.push_back(i.first);
    }
    for(auto i:fy)
    {
        if(i.second==my)
            vy.push_back(i.first);
    }
    for(int i=0;i<vx.size();i++)
    {
        for(int j=0;j<vy.size();j++)
        {
            if(p[make_pair(vx[i],vy[j])]==0)
                return cout<<mx+my,0;
        }
    }
    cout<<mx+my-1;
}


Measured memory_bytes: 56548
#include <bits/stdc++.h>
#include <stdio.h>
#include <math.h>
using namespace std;
using vi = vector<int>;
using vll = vector<long long int>;
using vb = vector<bool>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<long long int>>;
using ll = long long int;

ll dp[1000000];
vb ald(1000000,  false);
 
ll mem(ll i, const vvll &e){
    if(ald[i]){return dp[i];}
    if(e[i].size() == 0){return 0;}
    ll k = 0;
    for(auto x:e[i]){
        dp[x] = mem(x, e);
        ald[x] = true;
        if(dp[x] > k){k = dp[x];}
    }
    dp[i] = k+1;
    return k+1;
}

int main(){
    ll N, M; cin >> N >> M;
    vvll edge(N+1, vll(0));
    for(int i=0; i<M; i++){
        ll a, b; cin >> a >> b;
        edge[a].emplace_back(b);
    }

    for(int i=1; i<N+1; i++){
        dp[i] = 0;
    }

    for(int i=1; i<N+1; i++){
        dp[i] = mem(i, edge);
    }
    
    ll max = 0;

    for(int i=1; i<N+1; i++){
        if(max < dp[i]){max = dp[i];}
    }

    cout << max;
}

Measured memory_bytes: 9984
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
ss = input()
tds = [tuple(input().split()) for _ in range(Q)]

def isOKL(pos):
    for t, d in tds:
        if t == ss[pos]:
            if d == 'L':
                pos -= 1
                if pos < 0:
                    return False
            else:
                pos += 1
                if pos > N-1:
                    return True
    return True

def isOKR(pos):
    for t, d in tds:
        if t == ss[pos]:
            if d == 'L':
                pos -= 1
                if pos < 0:
                    return True
            else:
                pos += 1
                if pos > N-1:
                    return False
    return True

ng, ok = -1, N
while abs(ok-ng) > 1:
    mid = (ng+ok) // 2
    if isOKL(mid):
        ok = mid
    else:
        ng = mid
L = ok

ng, ok = N, -1
while abs(ok-ng) > 1:
    mid = (ng+ok) // 2
    if isOKR(mid):
        ok = mid
    else:
        ng = mid
R = ok

print(R-L+1)


Measured memory_bytes: 17652
#include <iostream>

using namespace std;

long long  gcd(long long a,long long b)
{
    long long c;
    while(b)
    {
        c=a%b;
        a=b;
        b=c;
    }
    return a;
}
int main()
{
  long long k,i,j,p,s=0;
  cin>>k;
  for(i=1;i<=k;i++)
  {
      for(j=1;j<=k;j++)
      {
          for(p=1;p<=k;p++)
          {
             s+=gcd(gcd(i,j),p);
          }
      }
  }
  cout<<s;
    return 0;
}


Measured memory_bytes: 3680
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;

int main()
{
	fastio;
	int n;
	scanf("%d",&n);
	int rem = n%10;
	if ( rem == 2 || rem == 4 || rem == 5 || rem == 7 || rem == 9 )
	cout << "hon";
	else if ( rem == 0 || rem == 1 || rem == 6 || rem == 8)
	cout << "pon";
	else
	cout << "bon";
	return 0;
}


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

using namespace std;
#define sz(a) int(a.size())
#define ll  long long int
#define mod (long long)(1e9+7)
#define endl '\n'
#define ENGZ ios::sync_with_stdio(0);ios_base::sync_with_stdio(0);cin.tie(0) , cout.tie(0) ;
#define pi (acos(-1))
#define F first
#define S second

ll fp(ll n , ll p )
{
    if(p==0)
        return 1;
    if(p==1)
        return n ;
    ll res = fp(n,p/2);
    res=((res)*(res)) ;
    if(p%2)
        res=(res*n) ;
    return res ;
}

// freopen ("myfile.txt","w",stdout);



int main()
{
    ENGZ;

    double w,h,x,y ;
    cin>>w >>h  >> x >> y ;
    long double ans = (w*h) ;
    ans/=2 ;
    bool f = 0 ;
    if(x == w/2.0 && y == h/2.0)f=1 ;
    cout<<setprecision(9) <<fixed ;
    cout<<ans <<"  " <<f <<endl ;

    return 0;
}


Measured memory_bytes: 3776