akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
#include<complex>
#include<numeric>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 998244353;
const ll INF = mod * mod;
typedef pair<int, int>P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);

ll mod_pow(ll a, ll n, ll m = mod) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }


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

int n;
string s;

int calc(int l, int len) {
	int t = 1;
	while (t <= len) {
		t *= 2;
	}
	t /= 2;
	//cout << l << " " << len << " " << t << endl;
	int res = 0;
	if (t == len) {
		for (int i = l; i < l + len && i < n; i++) {
			//cout << "?? " << i << endl;
			res ^= s[i] - '0';
		}
		return res;
	}
	int r = len - t;
	res = calc(l, r)^calc(l+t,r);
	return res;
}
void solve() {
	cin >> n >> s;
	string t; t.resize(n - 1);
	rep(i, n-1) {
		t[i] = '0'+abs(s[i] - s[i + 1]);
	}
	s = t; n = t.size();
	bool exi1 = false;
	rep(i, n)if (t[i] == '1')exi1 = true;
	if (!exi1) {
		int c = calc(0, n);
		if (c == 0)cout << 0 << endl;
		else cout << 2 << endl;
	}
	else {
		int c = calc(0, n);
		if (c%2)cout << 1 << endl;
		else cout << 0 << endl;
	}
}


signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(7);
	//init_f();
	//init();
	//int t; cin >> t; rep(i, t)solve();
	solve();
	stop
		return 0;
}

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

int main() {
    ll dp[10001];
    int h, n;
    cin >> h >> n;
    vector<ll> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }
    fill(dp, dp + 10001, 1e8);
    dp[0] = 0;
    for (int i = 0; i <= h; i++) {
        for (int j = 0; j < n; j++) {
            dp[i] = min(dp[i], dp[max(0ll, i - a[j])] + b[j]);
        }
    }
    cout << dp[h] << endl;
    return 0;
}

Measured memory_bytes: 384
package main

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

var sc = bufio.NewScanner(os.Stdin)

const INF = int(math.MaxInt32)
const INF64 = math.MaxInt64 / 2

func init() {
	sc.Buffer([]byte{}, math.MaxInt64)
	sc.Split(bufio.ScanWords)
}

func nextInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}
func nextStr() string {
	sc.Scan()
	if err := sc.Err(); err != nil {
		panic(err)
	}
	return sc.Text()
}

func abs(a int) int {
	return int(math.Abs(float64(a)))
}

func uniqIntSlice(a []int) []int {
	m := make(map[int]struct{})
	for _, v := range a {
		m[v] = struct{}{}
	}
	u := []int{}
	for k := range m {
		u = append(u, k)
	}
	return u
}
func min(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton min() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Min(float64(res), float64(nums[i])))
	}
	return res
}

func max(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton max() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Max(float64(res), float64(nums[i])))
	}
	return res
}

//a:old b:new a>b -> a=b (update) more small
func chmin(a *int, b int) bool {
	if *a > b {
		*a = b
		return true
	}
	return false
}

//a:old b:new a>b -> a=b (update) more small
func chmin64(a *int64, b int64) bool {
	if *a > b {
		*a = b
		return true
	}
	return false
}

//a:old b:new a<b -> a=b (update) more large
func chmax(a *int, b int) bool {
	if *a < b {
		*a = b
		return true
	}
	return false
}

//a:old b:new a<b -> a=b (update) more large
func chmax64(a *int64, b int64) bool {
	if *a < b {
		*a = b
		return true
	}
	return false
}

func main() {
	const V = 100100
	n := nextInt()
	w := int64(nextInt())
	wi := make([]int64, n)
	v := make([]int, n)
	for i := 0; i < n; i++ {
		wi[i] = int64(nextInt())
		v[i] = nextInt()
	}
	dp := make([][]int64, n+1)
	for i := 0; i < n+1; i++ {
		dp[i] = make([]int64, V)
		for j := 0; j < V; j++ {
			dp[i][j] = INF64
		}
	}
	dp[0][0] = 0

	for i := 0; i < n; i++ {
		for sum := 0; sum < V; sum++ {
			if sum-v[i] >= 0 {
				chmin64(&dp[i+1][sum], dp[i][sum-v[i]]+wi[i])
			}
			chmin64(&dp[i+1][sum], dp[i][sum])
		}
	}
	res := 0
	for s := 0; s < V; s++ {
		if dp[n][s] <= w {
			res = s
		}
	}
	fmt.Println(res)
}


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

int main() {
    int N;
    cin >> N;
    vector <int> p(N);
    for (int i=0; i<N; i++) cin >> p.at(i);
    vector <int> q = p;
    sort(q.begin(), q.end());
    bool isOK;
    for (int i=0; i<N; i++) {
        for (int j=i; j<N; j++) {
            vector <int> t = p;
            t.at(i)=p.at(j);
            t.at(j)=p.at(i);
            for (int i=0; i<N; i++) {
                if (t.at(i)!=q.at(i)) {
                    isOK = false;
                    break;
                }
            }
            if (isOK) {
                cout << "YES";
                return 0;
            }
            isOK=true;
        }
    }
    cout << "NO";
}

Measured memory_bytes: 256
#include<algorithm>
#include<bitset>
#include<climits>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<string>
#include<time.h>
#include<tuple>
#include<utility>
#include<vector>

using namespace std;
const long mod = 1000000007;

int main() { 
	 
	long H, W; cin >> H >> W;
	long res = 0;
	long A[509][509]; for (int i = 1; i <= H; i++) for (int j = 1; j <= W; j++) cin >> A[i][j];

	vector<pair<pair<long, long>, pair<long, long>>> oper;
	map<long, pair<long, long>> dic;

	long B[300009]; for (int i = 1; i <= H; i++) for (int j = 1; j <= W; j++) {
		long k = (i % 2 == 0) ? W - j + 1 : j;
		B[(i - 1) * W + k] = A[i][j];
		dic.insert(make_pair((i - 1) * W + k, make_pair(i, j)));
	}

	for (int i = 1; i < W * H; i++) {
		if (B[i] % 2 == 0) continue;

		res++;
        B[i + 1]++;
		oper.push_back(make_pair(dic.at(i), dic.at(i + 1)));
	}

	cout << res << endl;
	for (auto e : oper) cout << e.first.first << " " << e.first.second << " " << e.second.first << " " << e.second.second << endl;

}

Measured memory_bytes: 26100
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <numeric>
#include <array>
#include <cmath>
#include <memory>
using namespace std;
//変数デバッグ
#define DEB(variable) cout << #variable << '=' << variable << endl

//for簡易表記(引数ミス防止)
#define FOR(LoopVariable,numberOFbegin,numberOFend) for (int LoopVariable = (numberOFbegin); (LoopVariable) < (numberOFend); (LoopVariable)++)
#define DEFOR(LoopVariable,numberOFbegin,numberOFend) for (int LoopVariable = (numberOFbegin)-1; (LoopVariable) >= (numberOFend); (LoopVariable)--)
#define REP(LoopVariable,numberOFend) for(int LoopVariable = 0;(LoopVariable)<(numberOFend);LoopVariable++)

constexpr long long int linf = numeric_limits<long long int>::max()-5;
constexpr int inf= numeric_limits<int>::max()-5;
constexpr long long int mod = 1000000007;

int main(){

    int h, w;
    cin >> h >> w;
    vector<string> vs(h);

    REP(i,h){
        cin >> vs[i];
    }

    vector<bool> vh(h, false), vw(w, false);

    

    REP(i,h){
        REP(j,w){
            if(vs[i][j]=='#'){
                vh[i]=true;
                vw[j] = true;
            }
        }
    }
    bool endl_f;
    REP(i,h){
        endl_f = false;
        REP(j,w){
            if(vh[i]&&vw[j]){
                cout << vs[i][j];
                endl_f = true;
            }
        }
        if(endl_f){
            cout << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, begin, end) for (ll i = (begin); i < (end); i++)
#define REP(i, n) FOR(i, 0, n)
#define IFOR(i, begin, end) for (ll i = (begin)-1; i >= (end); i--)
#define IREP(i, n) IFOR(i, n, 0)
#define SORT(a) sort(a.begin(), a.end())
#define ISORT(a) sort(a.begin(), a.end(), greater<ll>())
#define REVERSE(a) reverse(a.begin(), a.end())
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v)                                          \
  cout << #v << "=(" << v[0];                              \
  FOR(i_debug, 1, v.size()) { cout << "," << v[i_debug]; } \
  cout << ")" << endl;
#define mdebug(m)                                                           \
  cout << #m << "=" << endl;                                                \
  REP(i_debug, m.size())                                                    \
  {                                                                         \
    REP(j_debug, m[i_debug].size()) { cout << m[i_debug][j_debug] << ","; } \
    cout << endl;                                                           \
  }
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)

#define ll long long
// #define f first
// #define s second
#define mp make_pair
#define pb push_back
#define INF 1000000000000000000

using vec = vector<ll>;
using mat = vector<vec>;
using Pii = pair<ll, ll>;
using PiP = pair<ll, Pii>;
using PPi = pair<Pii, ll>;
using bvec = vector<bool>;
using Pvec = vector<Pii>;

template <typename T>
void readv(vector<T> &a)
{
  REP(i, a.size())
  cin >> a[i];
}
void readv_m1(vector<int> &a)
{
  REP(i, a.size())
  {
    cin >> a[i];
    a[i]--;
  }
}

ll mod = 1000000007;

int main()
{
  ll N;
  cin >> N;
  // vec A(N);
  ll ans = 1;
  REP(i, N)
  {

    ll a;
    cin >> a;
    if (a == 0)
    {
      cout << 0 << endl;
      return 0;
    }
    else if (ans > 0)
    {
      if (log10(ans) + log10(a) > 18)
        ans = -1;
      else
      {
        ans *= a;
        if (ans > (ll)1e18)

          ans = -1;
      }
    }
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3932
#include<bits/stdc++.h>
using namespace std;
using p = pair<int,int>;
using pp = pair<p,int>;
using ll = long long;
const auto INF =(ll)1e5;

int main(){
  string s;
  cin >> s;
  for (int i = 0; i < s.size(); i++)
  {
    if(i%2==0){
      cout << s[i];
    }
  }
  
  
  return 0;
}

Measured memory_bytes: 512
import std.stdio,std.conv,std.string,std.algorithm;
 
void main(){
    auto k=readln.chomp.split.to!(int[])[0];
    auto a=readln.chomp.split.to!(int[]);
    int[] d;
    foreach(i;1..a.length){
        d~=a[i]-a[i-1];
    }   
    d~=a[0]+(k-a[$-1]);
    (k-max(d)).writeln;
}
 
auto max(int[] arr){
    int m;
    foreach(e;arr){
        if(m<=e)
            m=e;
    }   
    return m;
}

Measured memory_bytes: 11704
def digi(res):
    t = 1
    if res == 1:return (1,0)
    elif res>0:
        while True:
            if res<=((4**t)-1)//3:break
            t+=1
        r=res-4**(t-1)
        return (2*t-1,r)
    else:
        while True:
            if res>=-2*((4**t)-1)//3:break
            t+=1
        r=res-(-2*(4**(t-1)))
        return (2*t,r)
    
N = int(input())

if N == 0:print(0)
else:
    d = digi(N)
    ld = d[0]
    s=['0'] * d[0]
    s[0] = '1'

    while True:
        if d[1] != 0:
            d = digi(d[1])
            s[ld-d[0]]='1'
        else:break
    print(''.join(s))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <ext/rope>

using namespace std;
using namespace __gnu_cxx;

random_device rd;
mt19937 rnd(rd());
#define pt pair<int, int>
#define x first
#define y second
#define what_is(x) cerr << #x << " is " << x << endl;
#define ok cerr << "ok" << endl;
#define endl '\n'
#define int long long
#define ld long double

signed main()
{
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);

	int x = 100, ans = 0, n;
	cin >> n;
	while (x < n)
	{
		x += x / 100;
		++ans;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3664
#include <bits/stdc++.h>
#include<bitset>
using namespace std;
#define ios ios_base::sync_with_stdio(false);cin.tie(0);
#define setnow clock_t tStart;
#define setTime tStart = clock();
#define time0 (double)(clock() - tStart)/CLOCKS_PER_SEC
#define setin(x) ifstream cin(x);
#define setout(x) ofstream cout(x);
#define NMAX 30
typedef long long ll;
typedef long long int lli;
typedef pair < int, int> dbl;
const int maxInt = 1e9*2;
const lli maxLong = 1e18*2;

int main(){
        int n, sum = 0;
        cin >> n;
        for(int i=0;i<n;i++){
            int x;
            cin >> x;
            int k = 0;
            while(x%2==0){
                k++;
                x/=2;
            }
            sum += k;
        }
        cout << sum;
}


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

const int MAX_N = 100005;
int P[MAX_N];

int main()
{
	int N;
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		cin >> P[i];
		P[i]--;
	}

	set<int> s;
	int index[MAX_N];
	ll ans = 0;

	for (int i = 0; i < N; ++i)
	{
		index[P[i]] = i;
	}

	for (int x = N-1; x >= 0; --x)
	{
		int i = index[x];
		ll c;
		//calc c
		s.insert(i);
		int l[2] = {-1,-1};
		int r[2] = {N,N};

		//calc l
		auto it = s.find(i);
		for (int j = 0; j < 2; ++j)
		{
			if (it == s.begin()) break;
			it--;
			l[j] = *it;
		}

		//calc r
		it = s.find(i);
		for (int j = 0; j < 2; ++j)
		{
			it++;
			if (it == s.end()) break;
			r[j] = *it;
		}

		int ls[2],rs[2];
		ls[0] = i-l[0];
		ls[1] = l[0]-l[1];
		rs[0] = r[0]-i;
		rs[1] = r[1]-r[0];
		c = (ll)ls[0]*rs[1] + (ll)ls[1]*rs[0];

		ans += c * (x+1);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 5760
//Author : Sukarna Paul

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include<ext/pb_ds/detail/standard_policies.hpp>
#define pi acos(-1)
#define pb push_back
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define MAX 300005
#define INF 0x3f3f3f3f
template <class T> inline T bigmod(T p,T e,T M){ll ret = 1LL;for(; e > 0LL; e >>= 1LL){if(e & 1LL) ret = (ret * p) % M;p = (p * p) % M;}return (T)ret;}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}   // M is prime}

using namespace std;
using namespace __gnu_pbds;

typedef trie<string,null_type,trie_string_access_traits<>,pat_trie_tag,trie_prefix_search_node_update>pref_trie;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef tree<pair<int, int>,null_type,less<pair<int, int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;


int main(){
    IOS
    //freopen("output.txt","w",stdout);

    double r;
    cin>>r;
    cout<<2.0*pi*r<<"\n";
}


Measured memory_bytes: 3804
//Moh_K_Imar .......
//24/08/2020  ... 5,50.
//Ya Rab....
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
int main(){
    ll a,b,c;
    cin>>a>>b>>c;
    if(a+b+c>=22)cout<<"bust"<<endl;
    else 
        cout<<"win"<<endl;
    
    return 0;
}



Measured memory_bytes: 3584
N, K = [int(i) for i in input().split()]
D = [str(i) for i in input().split()]

payment = N
while True:
  count = 0
  for i in D:
    if i in str(payment):
      break
    else: 
      count += 1
  if count == len(D):
    print(payment)
    exit()
       
  payment += 1
  



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

int main() {
    int n;cin>>n;
    int a[n],ans=0;
    
    for(int i=0;i<n;++i){
        cin>>a[i];
        ans+=a[i]-1;
    }

    cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#define N 10000 
#define rep(a,i,n) for(ll i=(a);i<(n);i++)
typedef long long ll;

using namespace std;

ll str_len(char *s){
	ll len = 0;
	while(*s++)
		len++;
	return len;
}

bool palindrome(char *s,ll a,ll n){
	rep(a,i,n/2+1){
		if(s[i] != s[n-i-1])
			return false;
	}
	return true;
}

int main(){
	char s[N];
	cin >> s;
	ll n = str_len(s);
	if(palindrome(s,0,n)==true && palindrome(s,0,((n-1)/2))==true && palindrome(s,(n+1)/2,n)==true)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}

Measured memory_bytes: 256
import sys
import collections as c

input = sys.stdin.readline

def main():
    ans = 0
    n = int(input())
    d = list(map(int, input().split()))
    d.sort()
    g = d[n//2]
    items_count = c.Counter(d)
    gc = items_count[g]
    if gc == 1 or d[n//2-1] != g:
        ans += g - d[n//2-1]
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 14820
#include <iostream>

bool is_acgt(char c) {
    return c == 'A' || c == 'C' || c == 'G' || c == 'T';
}

int main() {
    std::string s;
    std::cin >> s;

    int max = 0;
    int count = 0;
    bool is_before_acgt = false;
    for (int i = 0; i < s.length(); i++) {
        if (is_acgt(s[i])) {
            count++;
            if (max < count) {
                max = count;
            }
        } else {
            count = 0;
        }
    }

    std::cout << max << std::endl;

    return 0;
}

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

using namespace std;

int main(void)
{
  string s;
  cin>>s;
  int size=s.length();
  
  if(s[size-1]=='s'){
    cout<<s<<"es"<<endl;
  }else{
    cout<<s<<"s"<<endl;
  }
  
  return 0;
}

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

namespace ConsoleApp21
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            string S = Console.ReadLine();
            int ans = 0;
            List<char> list = new List<char>();
            for (int i = 0; i < N; i++)
            {
                int sum = 0;
                list.Clear();
                string a = "", b = "";
                for (int j = 0; j < i; j++)
                {
                    a += S[j];
                }
                for (int j = i; j < N; j++)
                {
                    b += S[j];
                }
                for (int j = 0; j < a.Length; j++)
                {
                    if (!list.Contains(a[j]))
                    {
                        if (b.Contains(a[j])) { sum++; list.Add(a[j]); }
                    }
                }
                if (ans < sum) { ans = sum; }
            }
            Console.WriteLine(ans);
        }
    }
}


Measured memory_bytes: 13268
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
Bs=[]
for _ in range(M):
  Bs.append(list(map(int,input().split())))
Bs.sort(key=lambda x: x[1],reverse=True)

ans=0
Aid=0
Bid=0
Bcount=0
for _ in range(N):
  if Bid>=M or Bs[Bid][1]<A[Aid]:
    ans+=A[Aid]
    Aid+=1
  else:
    ans+=Bs[Bid][1]
    Bcount+=1
    if Bcount>=Bs[Bid][0]:
      Bcount=0
      Bid+=1
print(ans)

Measured memory_bytes: 32964
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define for_(i,n) for(int i=0;i<n;++i)
const int mod= 1e9 +7;
const int inf=1e7;
int n;



void updateTreeNode(vector<int> & tree,int p, int value)  
{  
    // set value at position p 
    tree[p+n] = value; 
    p = p+n; 
      
    // move upward and update parents 
    for (int i=p; i > 1; i >>= 1) 
        tree[i>>1] = max(tree[i],tree[i^1]); 
} 
  
// function to get sum on interval [l, r) 
int query(vector<int> & tree,int l, int r)  
{  
    int res = -inf; 
      
    // loop to find the sum in the range 
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) 
    { 
        if (l&1)  
            res = max(res,tree[l++]); 
      
        if (r&1)  
            res = max(res,tree[--r]); 
    } 
      
    return res; 
} 


main()
{  
 cin>>n;
int h[n],a[n];
//int t[4*n];
for_(i,n) cin>>h[i];
for_(i,n) cin>>a[i];
int dp[n];
//vector<int> dp(n+1, inf);
/*
LIS::
dp[i] = length of increasing subsequence when it ends at arr[i]
		     	Recurrence relation:	dp[i] = max(1,  max(dp[j] +1));
 where j: 0,1… i-1 and arr[j]<arr[i]
Modify LIS to accomodate beauty value

*/
vector<int> tree(2*n+2, -inf);
dp[0]= a[0];
//tree[h[0]]=dp[0];
updateTreeNode(tree,h[0],dp[0]);                                  

for(int i=1;i<n;++i)
{   int mxi= -inf;//a[i];
 
//    mxi=max(mxi,find_max(h[i],dp[])); 
/*
    for_(j,i){
        if(h[j]<h[i])
        mxi=max(mxi,dp[j]+a[i]);
    }
*/
//cout<<h[i]-1<<" ";cout<<endl;
//for_(i,2*n+2)    
//cout<<tree[i]<<"   ";
//cout<<endl;
mxi = max(a[i],query(tree,1,h[i])+a[i]);
dp[i]=mxi;
updateTreeNode(tree,h[i],dp[i]);
  
}

int ans=0;
for_(i,n)
{ans=max(ans,dp[i]);}
//cout<<endl;

cout<<ans<<endl;
//for_(i,2*n+2)    
//cout<<tree[i]<<"   ";
    
}























/*
typedef struct structure{
    int x,y;
} pt;
pt p0;
bool cmp(pt a, pt b)
{
    return cw(p0,a,b);
}
bool cw(pt a, pt b, pt c){
    return ((c.y-a.y)*(b.x-a.x)-(b.y-a.y)*(c.x-a.x))>=0
}



convex_hull(vector<pt>& points)
{
   // sort(points.begin(),points.end, cmp);// sorted according to y cordinate
    p0=points[0];
    sort(points.begin(),points.end, cmp);
    vector<pt> convexHull;
    stack<pt> temp;
    convexHull.push_back(points[0]);
    
    temp.push(points[0]);temp.push(points[1]);//temp.push(points[2]);
    pt top,top0;
    for(int it=2;it<points.size();++it)
    {   
        top=temp.top(); temp.pop(); top0=temp.top();
        pt next=points[it];
        if(cw(top0,top,next))
        {
            convexHull.push_back(top);
            temp.push(top);
            top0=top;
            top=next;
        }
        else
        {
          temp.push(next);  
        }
        
    }
    
}*/












Measured memory_bytes: 8064
#include <iostream>
using namespace std;
int w, h;
int c[55][55];

void dfs(int y, int x) {
    c[y][x] = 0;
    for (int dh = -1; dh <= 1; dh++) {
        for (int dw = -1; dw <= 1; dw++) {
            int nh = y + dh, nw = x + dw;
            if (0 <= nh && 0 <= nw && nh < h && nw < w && c[nh][nw]) {
                dfs(nh, nw);
            }
        }
    }
}

int main() {
    while (cin >> w >> h) {
        if (w == 0 && h == 0) break;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) cin >> c[i][j];
        }
        int ans = 0;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (c[i][j]) {
                    ans++;
                    dfs(i, j);
                }
            }
        }
        cout << ans << endl;
    }
}


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

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

   int n,g,b; cin >> n >> g >>b;
   int m = n * 100 + g * 10 + b;
   cout << ((0 == (m % 4)) ? "YES" : "NO");
   return 0;
}

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

int main(){
  int n,m;cin >>n>>m;
  vector<int> p(m),y(m);
  for(int i=0;i<m;i++)cin >>p[i] >>y[i];
  map<int,vector<int>> mp;
  for(int i=0;i<m;i++)mp[p[i]].push_back(y[i]);
  for(int i=0;i<mp.size();i++)sort(begin(mp[i]),end(mp[i]));
  for(int i=0;i<m;i++){
   int k=lower_bound(begin(mp[p[i]]),end(mp[p[i]]),y[i])-begin(mp[p[i]]);
    printf("%06d%06d\n",p[i],k+1);
  }
}


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

int main(){
 long long N,a,count2,count4,count;
  cin>>N;
  count=0;
  count2=0;
  count4=0;
  for(int i=0;i<N;i++){
cin>>a;
    if(a%2==1){
      count++;
    }
    else{
      if(a%4==0){
        count4++;
      }
      else{
        count2++;
      }
  }
  }

  if(count>count4+1){
    cout<<"No"<<endl;
    return 0;
  }
      if(count==count4+1&&count2!=0){
    cout<<"No"<<endl;
    return 0;
  }
     else{
    cout<<"Yes"<<endl;
    return 0;
  }
}

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

struct Node {
	int key;
	Node *right, *left, *parent;
};

Node *root, *NIL;

Node *treeMinimum(Node *x) {
	while (x->left != NIL) x = x->left;
	return x;
}

Node *find(Node *u, int k) {
	while (u != NIL && k != u->key) {
		if (k < u->key) u = u->left;
		else u = u->right;
	}
	return u;
}

Node *treeSuccessor(Node *x) {
	if (x->right != NIL) return treeMinimum(x->right);
	Node *y = x->parent;
	while (y != NIL && x == y->right) {
		x = y;
		y = y->parent;
	}
	return y;
}

void treeDelete(Node *z) {
	Node *y;
	Node *x;

	if (z->left == NIL || z->right == NIL) y = z;
	else y = treeSuccessor(z);

	if (y->left != NIL) {
		x = y->left;
	}
	else {
		x = y->right;
	}

	if (x != NIL) {
		x->parent = y->parent;
	}

	if (y->parent == NIL) {
		root = x;
	}
	else {
		if (y == y->parent->left) {
			y->parent->left = x;
		}
		else {
			y->parent->right = x;
		}
	}

	if (y != z) {
		z->key = y->key;
	}

	free(y);
}

void insert(int k) {
	Node *y = NIL;
	Node *x = root;
	Node *z;

	z = (Node *)malloc(sizeof(Node));
	z->key = k;
	z->left = NIL;
	z->right = NIL;

	while (x != NIL) {
		y = x;
		if (z->key < x->key) {
			x = x->left;
		}
		else {
			x = x->right;
		}
	}

	z->parent = y;
	if (y == NIL) {
		root = z;
	}
	else {
		if (z->key < y->key) {
			y->left = z;
		}
		else {
			y->right = z;
		}
	}
}

void inorder(Node *u) {
	if (u == NIL) return;
	inorder(u->left);
	printf(" %d", u->key);
	inorder(u->right);
}
void preorder(Node *u) {
	if (u == NIL) return;
	printf(" %d", u->key);
	preorder(u->left);
	preorder(u->right);
}

int main() {
	int n, x;
	string com;

	scanf("%d", &n);

	for (int i = 0; i < n; ++i) {
		cin >> com;
		if (com[0] == 'f') {
			scanf("%d", &x);
			Node *t = find(root, x);
			if (t != NIL) printf("yes\n");
			else printf("no\n");
		}
		else if (com == "insert") {
			scanf("%d", &x);
			insert(x);
		}
		else if (com == "print") {
			inorder(root);
			printf("\n");
			preorder(root);
			printf("\n");
		}
		else if (com == "delete") {
			scanf("%d", &x);
			treeDelete(find(root, x));
		}
	}

	free(root);
	free(NIL);
}


Measured memory_bytes: 22052
#include<stdio.h>
#include<stdlib.h>


int main(){
  int mini;
  int *A;
  int j,i;
  int num;
  int N;
  int sum=0;
  int flag;

  scanf("%d",&N);
  A=(int *)malloc(num*sizeof(int));
  for(j=0;j<N;j++)
    scanf("%d",&A[j]);

  for(i=0;i<N;i++){
    mini=i;
    flag=0;
    for(j=i;j<N;j++){
      if(A[j]<A[mini]){
	mini=j;
	flag=1;
      
      }
    }
    if(flag){
      num=A[i];
      A[i]=A[mini];
      A[mini]=num;
      sum++;
    }
     
  }
  
  for(j=0;j<N-1;j++)printf("%d ",A[j]);
  printf("%d\n%d\n",A[j],sum);
  


  
  return 0;
}
  
  



Measured memory_bytes: 2100
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;

public class Main {
  private static String GOAL = "01234567";
  private static int[][] MOVE_LIST = {
      { 1, 4 },
      { 0, 2, 5 },
      { 1, 3, 6 },
      { 2, 7 },
      { 0, 5 },
      { 1, 4, 6 },
      { 2, 5, 7 },
      { 3, 6 }
  };

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    Map<String, Integer> answers = breathFirstSearch();

    while (true) {
      String map = br.readLine();
      if (map == null) {
        break;
      }
      System.out.println(answers.get(removeSpace(map)));
    }
  }

  private static String removeSpace(String map) {
    String[] newMap = map.split(" ");
    return Arrays.asList(newMap).stream().collect(Collectors.joining());
  }

  private static Map<String, Integer> breathFirstSearch() {
    Map<String, Integer> answers = new HashMap<>();
    answers.put(GOAL, 0);

    Deque<String> queues = new LinkedList<>();
    queues.add(GOAL);

    while (true) {
      if (queues.size() == 0) {
        break;
      }

      String search = queues.pop();

      int index = search.indexOf('0');
      for (int nextId : MOVE_LIST[index]) {
        String[] newMap = search.split("");
        newMap[index] = newMap[nextId];
        newMap[nextId] = "0";
        String nextMap = Arrays.stream(newMap).collect(Collectors.joining());
        if (answers.get(nextMap) == null) {
          int count = answers.get(search);
          answers.put(nextMap, count + 1);
          queues.add(nextMap);
        }
      }
    }

    return answers;
  }
}

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

int main(){
  int N ; 
  cin >> N ; 
  map<long long , long long> A ; 
  for(int i = 0 ; i < N ; i++){
    long long P ; 
    cin >> P ; 
    A[P]++ ;
  }
  

  long long X = 0 , Y  = 0; 
  for(auto a : A){
    if( a.second >= 2 && X <= a.first) {
      Y = X ; 
      X = a.first ;
    	if( a.second >=4 && X<= a.first){
      		X = a.first; 
      		Y = a.first ; 
    	}
    }
    
  }
  
  cout << X*Y << endl ; 
}

Measured memory_bytes: 9772
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<unordered_map>
#include<set>
#include<cmath>
#include<stack>
#include<cstdio>
using namespace std;
int main()
{
    int n,m,ans,left=0,right=0;
    string s;
    cin>>n>>m;
    if(n==1)
        left=0;
    else
    {
        for(int i=1;i<n;i++)
            left+=i;
    }
    if(m==1)
        right=0;
    else
    {
        for(int i=1;i<m;i++)
            right+=i;
    }
    ans=left+right;//n为偶数，m为奇数，奇奇为偶，偶偶为偶，算这两个
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
use std::io::Read;

fn run() {
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    let n: usize = it.next().unwrap().parse().unwrap();
    let k: usize = it.next().unwrap().parse().unwrap();
    let mut a = vec![];
    let mut b = vec![];
    let mut zero = 0usize;
    for s in it {
        let x: i64 = s.parse().unwrap();
        if x == 0 {
            zero += 1;
        } else if x > 0 {
            a.push(x);
        } else {
            b.push(x);
        }
    }
    a.sort();
    b.sort();
    b.reverse();
    let count = |m: i64| -> usize {
        let mut cnt = if m >= 0 {zero * (zero - 1) / 2 + zero * (n - zero)} else {0};
        let mut j = a.len();
        let mut add = 0;
        for &x in a.iter() {
            while j > 0 && x * a[j - 1] > m {
                j -= 1;
            }
            add += j;
            if x * x <= m {
                add -= 1;
            }
        }
        let mut j = b.len();
        for &x in b.iter() {
            while j > 0 && x * b[j - 1] > m {
                j -= 1;
            }
            add += j;
            if x * x <= m {
                add -= 1;
            }
        }
        cnt += add / 2;
        let mut j = 0;
        for &x in b.iter().rev() {
            while j < a.len() && x * a[j] > m {
                j += 1;
            }
            cnt += a.len() - j;
        }
        cnt
    };
    let mut ng = -1_000_000_000_000_000_000 - 1;
    let mut ok = 1_000_000_000_000_000_000;
    while ok - ng > 1 {
        let m = (ok + ng) / 2;
        if count(m) >= k {
            ok = m;
        } else {
            ng = m;
        }
    }
    println!("{}", ok);
}

fn main() {
    run();
}


Measured memory_bytes: 10492
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
C = [list(map(int,input().split())) for i in range(n-1+m)]

r = -1
R = [1] * (n+1)
for i in range(len(C)):
    R[C[i][1]] = 0
for i in range(1, n+1):
    if R[i] == 1:
        r = i

# print(r)

F = [0] * (n+1)
P = [0] * (n+1)

M = [[] for i in range(n+1)]
for i in range(n-1+m):
    M[C[i][0]].append(C[i][1])
    F[C[i][1]] += 1

# 1始まりの場合
Q = [r]
s = 0
# V[r] = 1
while s < len(Q):
    i = Q[s]
    for x in M[i]:
        F[x] -= 1
        if F[x] == 0:
            P[x] = i
            Q.append(x)
    s += 1
# print(P)

for i in range(1, n+1):
    print(P[i])

Measured memory_bytes: 77788
#include <cstdio>
using namespace std;

int main(){
	char str[10];
	int r[3], c[3], d1, d2;
	bool judged;
	
	while((scanf("%s", str)) != EOF){
		for(int i = 0; i < 3; i++){
			r[i] = 0; c[i] = 0;
		}
		d1 = 0; d2 = 0;
		
		for(int i = 0; i < 9; i++){
			if(str[i] == 'o'){
				c[i / 3]++;
				r[i % 3]++;
				if(i / 3 == i % 3) d1++;
				if(i / 3 + i % 3 == 2) d2++;
			}
			else if(str[i] == 'x'){
				c[i / 3]--;
				r[i % 3]--;
				if(i / 3 == i % 3) d1--;
				if(i / 3 + i % 3 == 2) d2--;
			}
		}
		
		judged = false;
		for(int i = 0; i < 3; i++){
			if(r[i] == 3 || c[i] == 3){
				judged = true;
				printf("o\n");
				break;
			}
			if(r[i] == -3 || c[i] == -3){
				judged = true;
				printf("x\n");
				break;
			}
		}
		if(!judged){
			if(d1 == 3 || d2 == 3){
				judged = true;
				printf("o\n");
			}
			else if(d1 == -3 || d2 == -3){
				judged = true;
				printf("x\n");
			}
		}
		if(!judged){
			printf("d\n");
		}
	}
	
	return 0;
}

Measured memory_bytes: 948
#include <stdarg.h>
#include <stdio.h>
#include <string.h>

long long max(int len, ...) {
    long long i, _max, num;
    va_list ap;
    va_start(ap, len);
 
    _max = va_arg(ap, long long);
    for (i = 1; i < len; i++) {
        num = va_arg(ap, long long);
        if (num > _max)
            _max = num;
    }
    va_end(ap);
    return _max;
}
long long min(int len, ...) {
    long long i, _min, num;
    va_list ap;
    va_start(ap, len);
 
    _min = va_arg(ap, long long);
    for (i = 1; i < len; i++) {
        num = va_arg(ap, long long);
        if (num < _min)
            _min = num;
    }
    va_end(ap);
    return _min;
}
int main(void) {
    int i, j, k, N;
    long long W, res, l, w0, w[110], v[110], dp[110][310];
    scanf("%d%lld", &N, &W);
    for (i=0;i<N;i++) scanf("%lld%lld", &w[i], &v[i]);
    w0 = w[0];
    for (i=0;i<N;i++) w[i] -= w0;

    memset(dp,-1,sizeof(dp));
    dp[0][0] = 0;
    dp[1][0] = v[0];
    for (i=1;i<N;i++) {
        for (j=i;j>=0;j--) {
            for (k=299-w[i];k>=0;k--) {
                if (dp[j][k] != -1) dp[j+1][k+w[i]] = max(2,dp[j+1][k+w[i]],dp[j][k]+v[i]);
            }
        }
    }
    res = -1LL;
    for (i=0;i<=N;i++) {
        for (l=min(2,299,W-w0*i);l>=0;l--) res = max(2,res,dp[i][l]);
    }
    printf("%lld\n", res);
    return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<limits.h>

#define ll long long

using namespace std;

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

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

	cout << 2 * N - 2 << endl;

	auto pitr = minmax_element(a.begin(), a.end());
	int min_v = *pitr.first;
	int max_v = *pitr.second;
	auto min_i = distance(a.begin(), pitr.first);
	auto max_i = distance(a.begin(), pitr.second);
	if (min_v >= 0 || abs(min_v) < max_v) {
		for (int i = 0; i < N; i++) {
			if (i == max_i) continue;
			cout << max_i + 1 << " " << i + 1 << endl;
			a[i] += max_v;
		}
		for (int i = 1; i < N; i++) {
			cout << i - 1 + 1 << " " << i + 1 << endl;
			a[i] += a[i - 1];
		}
	}
	else {
		for (int i = N - 1; i >= 0; i--) {
			if (i == min_i) continue;
			cout << min_i + 1 << " " << i + 1 << endl;
			a[i] += min_v;
		}
		for (int i = N - 2; i >= 0; i--) {
			cout << i + 1 + 1<< " " << i + 1<< endl;
			a[i] += a[i + 1];
		}
	}

	system("pause");
	return 0;
}

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

using namespace std;

#define forn(i,n) for ( int i=0 ; i < n ; i++ )
#define all(a) (a).begin(), (a).end()
#define lb lower_bound
#define ub upper_bound
#define vi vector<int >
#define pii pair<int, int>
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define SQ(a) (a)*(a)
#define ll long long
#define lli long long int
#define ull unsigned long long
#define endl '\n'
#define Pi(a) printf("%d\n",a);
#define debug2(a,b) printf("%d\t%d\n",a,b);
#define debug1(a) printf("%d\n",a);
#define Si(a) scanf("%d",&a);
#define mod 1000000007
#define w(n) while(n--)


#ifdef DEBUG
     #define debug(args...)            {dbg,args; cerr<<endl;}
#else
    #define debug(args...)              // Just strip off all debug tokens
#endif

struct debugger
{
    template<typename T> debugger& operator , (const T& v)
    {    
        cerr<<v<<" ";    
        return *this;    
    }
} dbg;



int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	//code	
    int n,m;
    cin >> n >> m;
    lli arr[1001][3];
    forn(i,n){
        cin >> arr[i][0] >> arr[i][1] >> arr[i][2];
    }
    lli ans=0;
    std::vector<lli> v;
    forn(i,8){
    	int a,b,c;
    	i&(1<<0) ? a=1 : a=-1;
    	i&(1<<1) ? b=1 : b=-1;
    	i&(1<<2) ? c=1 : c=-1;
    	//cout << a << " " << b << " " << c << endl;
    	v.clear();
    	forn(j,n){
    		v.PB(a*arr[j][0]+b*arr[j][1]+c*arr[j][2]);
    	}
    	sort(all(v));
    	lli local=0;
    	int k=v.size()-1;
    	int l=0;
    	while(l<m){
    		local+=v[k];
    		k--;
    		l++;
    	}
    	ans=max(ans,local);
    }
    cout << ans;
	
	return 0;

}



Measured memory_bytes: 256
N = int(input())
S1 = input()
S2 = input()
S = S1 + "0"
ans = 3
status = ""
i = 0
while i<N:
    if S[i]==S[i+1]:
        if status == "y":
            ans *= 3
        else:
            ans *= 2
        status = "y"
        i += 2
    else:
        if status == "t":
            ans *= 2
        status = "t"
        i += 1
    ans %= 1000000007
print(ans)


Measured memory_bytes: 3060
n=int(input())
l=list(map(int,input().split()))
if n<=2:
    print(0)
else:
    count=0
    for i in range(n):
        for j in range(i+1,n):
            for k in range(j+1,n):
                if l[i]!=l[j] and l[j]!=l[k] and l[k]!=l[i]:
                    a=[l[i],l[j],l[k]]
                    a.sort()
                    if a[2]<a[0]+a[1]:
                        count+=1
    print(count)

Measured memory_bytes: 9120
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define rREP(i,m,n) for(ll i = (m); i >= (n); i--)
#define ALL(c) (c).begin(), (c).end()
#define print(x) cout << (x) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    string s;
    cin>>s;
    bool flag = true;
    rep(i,n/2)
    {
        if(s[i]!=s[i+n/2])
        {
            flag = false;
            break;
        }
    }
    if (n%2==1)
    {
        flag = false;
    }
    
    if(flag)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    
    
    
}




Measured memory_bytes: 256
import java.util.Scanner;

class Main{
    static void sortPrint(int[] a, int n){
        for(int i = 0; i < n - 1; i++){
            System.out.print(a[i] + " ");
        }
        System.out.println(a[n - 1]);
    }

    static void insertionSort(int[] a, int n){
        for(int i = 1; i < n; i++){
            int v = a[i];
            int j = i - 1;
            while(j >= 0 && a[j] > v){
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = v;
            sortPrint(a,n);
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];

        for(int i = 0; i < n; i++)
            a[i] = sc.nextInt();

        sortPrint(a,n);
        insertionSort(a,n);
    }
}


Measured memory_bytes: 31788
#include <bits/stdc++.h>
#define N 1000010
using namespace std;
pair<int,int> tmp;
map<pair<int,int>,int> ind;
vector<pair<int,int> > vt[N];
priority_queue<pair<int,int> > pq;
bool book[N];
int n,m,nd,dist[N];
int main(){
	int x,y,a,b,c,i,j;
	cin>>n>>m;
	nd=n;
	for(i=0;i<m;i++)
	{
		cin>>x>>y>>c;
		x--;
		y--;
		tmp=make_pair(x,c);
		if(ind[tmp]!=0)
		{
			a=ind[tmp];
		}
		else
		{
			a=nd;
			ind[tmp]=nd;
			nd++;
		}
		vt[x].push_back(make_pair(a,1));
		vt[a].push_back(make_pair(x,0));
		tmp=make_pair(y,c);
		if(ind[tmp]!=0)
		{
			b=ind[tmp];
		}
		else
		{
			b=nd;
			ind[tmp]=nd;
			nd++;
		}
		vt[y].push_back(make_pair(b,1));
		vt[b].push_back(make_pair(y,0));
		vt[a].push_back(make_pair(b,0));
		vt[b].push_back(make_pair(a,0));
	}
	/*for(i=0;i<nd;i++)
	{
		for(j=0;j<vt[i].size();j++)
		{
			cout<<i<<"--"<<vt[i][j].second<<"-->"<<vt[i][j].first<<endl;
		}
	}*/
	pq.push(make_pair(0,0));
	while(!pq.empty())
	{
		c=-(pq.top().first);
		x=pq.top().second;
		pq.pop();
		if(book[x])
		{
			continue;
		}
		book[x]=true;
		if(x==n-1)
		{
			cout<<c<<endl;
			return 0;
		}
		for(i=0;i<vt[x].size();i++)
		{
			pq.push(make_pair(-(c+vt[x][i].second),vt[x][i].first));
		}
	}
	cout<<-1<<endl;
	return 0;
}

Measured memory_bytes: 71800
def solve(H, W, S):
    for h in range(1, H):
        for w in range(1, W):
            if S[h][w] == '#':
                if not (S[h-1][w] == '#' or S[h+1][w] == '#' or S[h][w+1] == '#' or S[h][w-1] == '#'):
                    return "No"
    return "Yes"


H, W = [int(x) for x in input().split()]
# H, W < 50
S = []
S.append('.' * (W+2))
for _ in range(H):
    S.append("."+input().strip()+".")
S.append('.' * (W+2))
import sys
for row in S:
    print(row, file=sys.stderr)
print(solve(H, W, S))



Measured memory_bytes: 3064
#include <iostream>
using namespace std;
int main() {
  int A, B, C, D, E, F;
  cin >> A >> B >> C >> D >> E >> F;
  A *= 100;
  B *= 100;
  int water;
  int suger, max_suger{0};
  int all, max_all{0};
  double dens, max_dens{-1.0};
  double limit_dens{E / (100.0 + E)};
  for (int a{0}; a <= F; a += A) {
    for (int b{0}; a + b <= F; b += B) {
      water = a + b;
      for (int c{(F - water) / C}; c >= 0; --c) {
        for (int d{(F - (water + c * C)) / D}; d >= 0; --d) {
          suger = c * C + d * D;
          all = water + suger;
          dens = static_cast<double>(suger) / all;
          if (dens > limit_dens) continue;
          if (max_dens < dens) {
            max_all = all;
            max_suger = suger;
            max_dens = dens;
            break;
          }
        }
      }
    }
  }

  cout << max_all << " " << max_suger << "\n";
  return 0;
}


Measured memory_bytes: 504
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int G, R;
  cin >> R >> G;
  cout << 2 * G - R << endl;
  return 0;
}

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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
#define print(x) cout<<'>'<<#x<<':'<<x<<endl;
#define mod 1000000007

void solve(){

    string a,b;
    cin>>a>>b;
    if ((int)(sqrt(stoi(a+b))*(int)sqrt(stoi(a+b)))==stoi(a+b)){
        cout<<"Yes";
    }else cout<<"No";
}

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

    return 0;
}




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

int ans[101][101];
int a[101];
int main() {
  int h, w, n;
  cin >> h >> w >> n;
  rep(i, 0, n) cin >> a[i];

  int now = 0;
  rep(i, 0, h) {
    vector<int> tmp;
    rep(j, 0, w) {
      tmp.push_back(now + 1);
      now += --a[now] == 0;
    }
    if (i & 1) reverse(tmp.begin(), tmp.end());
    rep(j, 0, w) cout << tmp[j] << " \n"[j == w - 1];
  }

  return 0;
}


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

int main() {
    int n, s=0, odd=0;
    cin >> n;
    for(int i=0;i<n;i++){
        int a;
        cin >> a;
        s ^= a;
        odd |= a&1;
    }
    cout << (s == 1 || (s == 0 && odd == 0) ? "Bob" : "Alice") << endl;
    return 0;
}



Measured memory_bytes: 3112
/*    
 *  eat_code    
 *  IIIT Allahabad
 */
#include <bits/stdc++.h>
//#include "pretty_print.h"
using namespace std;

#define mp make_pair
#define mt make_tuple
#define pb push_back
#define CONTAINS(a, x) (a.find(x) != a.end())
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)x.size()
#define nl cout << endl
#define F first
#define S second

#define what_is(x) cout << #x << " = " << x << endl
#define boost ios::sync_with_stdio(false);cin.tie(NULL)
#define CASET int ___T, case_n = 1; cin >> ___T; while (___T-- > 0) 


#define rep(it, st, en) for(ll it = st; it < en; it++)
#define rep1(it, st, en) for(ll it = st; it <= en; it++)
#define per(it, st, en) for(ll it = en - 1; it >= st; it--)

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

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<ii> vii;
typedef vector<vi> vvi;

ll INF = 1E9;
ll M = 1E9 + 7;

inline ll power (ll a,ll p){
    ll res = 1, x = a;
    while ( p ) {
        if ( p & 1 ) res = ( res * x );
        x = ( x * x ); p >>= 1;
    }
    return res;
}

template <typename T> ostream& operator<<(ostream& os, const vector<T> &p){os << "[ "; for (T x: p) os << x << " "; os << "]" << endl; return os;}
template <typename T> ostream& operator<<(ostream& os, const set<T> &p){os << "{ "; for (T x: p) os << x << " "; os << "}" << endl; return os;}
template <typename Tk, typename Tv> ostream& operator<<(ostream& os, const map<Tk, Tv> &p){os << "{ "; for (pair<Tk, Tv> x: p) os << x << " "; os << "}" << endl; return os;}
template <typename Tk, typename Tv> ostream& operator<<(ostream& os, const pair<Tk, Tv> &p){os << "{" << p.first << ',' << p.second << "}";return os;}

int main() {
    boost;
    if(fopen("input.txt", "r")){
      freopen("input.txt", "r", stdin);
      freopen("output.txt", "w", stdout);
    }
    ll q, h, s, d, n;
    cin >> q >> h >> s >> d >> n;
    //for 1 l efficient;
    ll min1L = min(q * 4, min(q * 2 + h, min(2 * h, s)));
    ll min2L = min(2 * min1L, d);
    ll ones = n, twos = n / 2, rem = n % 2;
    ll ans = ones * min1L;
    if(twos * 2 + rem == n)ans = min(ans, twos * min2L + rem * min1L);
    cout << ans << "\n";

    return 0;
}
//  Train Insane or Remain the same
 

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

int main()
{
  const char sort_list[5] = "SHCD";
  int n;
  char sort;
  int num;
  bool card[4][13] = { false };

  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> sort >> num;
    for (int i = 0; i < 4; i++) 
      if (sort == sort_list[i]) card[i][num-1] = true;
  }
  for (int i = 0; i < 4; i++)
    for (int j = 0; j < 13; j++)
      if (!card[i][j]) cout << sort_list[i] << " " << j+1 << endl;

  return 0;
}


Measured memory_bytes: 3052