akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
 #define MAX 1000000000005
 #define ll long long int
 int main()
 {    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  

        long long int m,sum=0,k=0,i,j,x=0,sum1=0,l,kk,y,z,e,f,q=MAX,r=MAX,n;
          cin>>n>>m;
           cout<<n*m<<endl;
     }
 

Measured memory_bytes: 3648
#include<stdio.h>

int main()
{
    int i,j,n;
    static char prime[10000001];

    for(i = 2;i < 10000000;i++) prime[i]=1;

    for(i = 2;i <= 10000000;i++) if(prime[i]) for(j=i+i;j<=10000000;j+=i) prime[j]=0;

    while(scanf("%d",&n),n){

        if(n%2==0)n--;

        for(i=n;i>13;i-=2){
            if(prime[i]+prime[i-2]+prime[i-6]+prime[i-8]==4) {
                break;
            }   
        }   

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

    }   
    return 0;
}

Measured memory_bytes: 10360
h,w=map(int,input().split())
s=[input() for i in range(h)]


for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            print("#",end="")
        else:
            cnt=0
            for x in range(-1,2):
                for y in range(-1,2):
                    if 0<=i+x<h and 0<=j+y<w and s[i+x][j+y]=="#":
                        cnt+=1
            print(cnt,end="")
    print()

Measured memory_bytes: 3572
import java.net.CookieHandler;
import java.util.*;

public class Main {

	private static List<Long> getStrings(Scanner sc, long num) {
		List<Long> stringList = new ArrayList<>();
		while(num>0) {
			long nextInt = sc.nextLong();
			stringList.add(nextInt);
			num--;
		}
		return stringList;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long x = sc.nextLong();
		long y = sc.nextLong();
		long a = sc.nextLong();
		long b = sc.nextLong();
		long c = sc.nextLong();
		List<Long> aArray = getStrings(sc, a);
		List<Long> bArray = getStrings(sc, b);
		List<Long> cArray = getStrings(sc, c);
		Collections.sort(aArray);
		Collections.reverse(aArray);
		Collections.sort(bArray);
		Collections.reverse(bArray);
		Collections.sort(cArray);
		Collections.reverse(cArray);

		List<Long> allArray = new ArrayList<>();
		allArray.addAll(aArray.subList(0, (int)x));
		allArray.addAll(bArray.subList(0, (int)y));
		allArray.addAll(cArray);
		Collections.sort(allArray);
		Collections.reverse(allArray);
		long sum = 0;
		for (int i = 0; i < x+y; i++) {
			sum+=allArray.get(i);
		}

		System.out.println(sum);
	}

}


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

struct edge{
	int64_t to, cost;

	edge(int64_t to, int64_t cost){
		this->to = to;
		this->cost = cost;
	}
};

signed main(){
	int n, m, r;
	cin >> n >> m >> r;
	int t[r];
	for(int &i:t){
		cin >> i;
		i--;
	}
	sort(t, t + r);
	int64_t cost[n][n];
	fill(cost[0], cost[n], 1ll << 60);
	while(m--){
		int64_t a, b, c;
		cin >> a >> b >> c;
		a--;
		b--;
		cost[a][b] = cost[b][a] = c;
	}
	for(int i = 0; i < n; i++) cost[i][i] = 0;
	for(int k = 0; k < n; k++) for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
	int64_t ans = 1ll << 60;
	do{
		int64_t tmp = 0;
		for(int i = 1; i < r; i++) tmp += cost[t[i - 1]][t[i]];
		ans = min(ans, tmp);
	}while(next_permutation(t, t + r));
	cout << ans << endl;
}

Measured memory_bytes: 512
N = int(input())
A = list(map(int,input().split()))
sum = 0
for i in range(1,N): #2番目から最後尾まで
    lows = A[i]-A[i-1] #1つ前の人との身長差
    if lows < 0:
        sum += -lows
        A[i] += -lows

print(sum)


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

#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

int main() {
    int64_t n;
    array<int64_t, 3> a;
    cin >> n >> a[0] >> a[1] >> a[2];

    vector<int64_t> ans;
    int64_t pi = -1, pj = -1;
    for (auto _ : irange(0L, n)) {
        string s;
        cin >> s;

        int64_t i = s[0] - 'A';
        int64_t j = s[1] - 'A';

        if (a[i] == 0 && a[j] == 0) {
            if (pi >= 0) {
                swap(a[pi], a[pj]);
                ans.back() = pj;
            }
        }

        if (a[i] == 0 && a[j] == 0) {
            cout << "No" << endl;
            return 0;
        }

        if (a[i] == 1 && a[j] == 1) {
            pi = i;
            pj = j;
            ++a[i];
            --a[j];
            ans.push_back(i);
            continue;
        }

        pi = -1;
        pj = -1;

        if (a[i] < a[j]) {
            ++a[i];
            --a[j];
            ans.push_back(i);
        } else {
            --a[i];
            ++a[j];
            ans.push_back(j);
            continue;
        }
    }

    cout << "Yes" << endl;
    for (auto i : ans) {
        cout << (char)(i + 'A') << "\n";
    }
}

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

using namespace std;

int main(){
  int N;
  vector<int> a;
  cin >> N;
  for (int i = 0; i < N; i++){
    int tmp;
    cin >> tmp;
    a.push_back(tmp);
  }
  sort(a.begin(), a.end(), greater<int>());

  int Alice=0,Bob=0;
  for (int i = 0; i < N; i++){
    if(i%2 == 0){
      Alice += a[i];
    }else{
      Bob += a[i];
    }
  }

  printf("%d\n", Alice - Bob);
  
}


Measured memory_bytes: 3712
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>;
using namespace std;
string s;
int main(){
    cin>>s;
	int k=s.size();
    if(k%2!=0){
        printf("No");
        return 0;
	}
    for(int i=0;i<k/2;i++){
    	int u=abs(s[i]-s[k-i-1]);
        if(u!=1&&u!=2){
        	printf("No");
            return 0;
		}
    }
    printf("Yes");
    return 0;
}

Measured memory_bytes: 512
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define OUT(x) cout << (x) << endl
typedef long long ll;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if (a + b + c >= 22)
        OUT("bust");
    else
        OUT("win");
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		try (Scanner scan = new Scanner(System.in)) {

			int n = scan.nextInt();
			
			int ans = 0;
			
			String cur = scan.next();
			
			String[] a = cur.split("");
			
			String preCol = "";
			for(String c:a) {
				
				if(!preCol.equals(c)) {
					ans++;
				}
				
				preCol = c;
			}
			
			System.out.println(ans);
		}
	}
}

Measured memory_bytes: 32600
#include <stdio.h>
#include <math.h>

int main(int argc, const char * argv[]) {
    // insert code here...
    int a;
    int b;
    int c;
    scanf("%d",&a);
    scanf("%d",&b);
    c=a%2;
    if(c==0){
        if(b*2<=a){
            printf("YES");
        }
        else printf("NO");
    }
    else{
        if(b*2-1<=a){
            printf("YES");
        }
        else printf("NO");
    }
    return 0;
}


Measured memory_bytes: 128
#include <iostream>

using namespace std;

int main() {
	int A, B;
	cin >> A >> B;

	int ans = -1;
	if (1 <= A && A <= 9 && 1 <= B && B <= 9) {
		ans = A * B;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3644
<?php

$input = trim(fgets(STDIN));

List($W, $H, $x, $y, $r) = explode(" ", $input);

$x1 = $r;
$y1 = $H - $r;
$x2 = $W - $r;
$y2 = $r;

if ($x1 <= $x and $x <= $x2 and $y2 <= $y and $y <= $y1) {
  echo "Yes".PHP_EOL;
} else {
  echo "No".PHP_EOL;
}

Measured memory_bytes: 15384
#include<iostream>
#include<cstdlib>

using namespace std;

int main() {
	int x, a, b;
	cin >> x >> a >> b;
	
	if (abs(x - a )< abs(x - b)) {
		cout << 'A' << endl;
	}
	else{
		cout << 'B' << endl;
	}

	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		final Scanner sc = new Scanner(System.in); 
		int n=sc.nextInt();
		int[][] graph=new int[n+1][n+1];
		for(int i=0;i<n;i++){
			int u=sc.nextInt();
			int k=sc.nextInt();
			for(int j=0;j<k;j++){
			graph[u][sc.nextInt()]++;
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(j==n) System.out.println(graph[i][j]);
				else System.out.print(graph[i][j]+" ");
			}
		}
	}
}

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

int main() {
    int n,k,x,y;
    cin>>n>>k>>x>>y;
    long ans=0;
    if(k>=n)ans=n*x;
    else ans=k*x+(n-k)*y;
    cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
// "header" {{{
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <tuple>
#include <iomanip>

using namespace std;

#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int> 
#define int int64_t
#define Fixed fixed << setprecision(10)
#define moke_pair make_pair
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const long long mod = 1000000007;

template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
template <class T,class U> using umap = unordered_map<T,U>;

inline int64_t updiv(int64_t n,int64_t d){
    return ((n + d -1) / d);
}
/*
inline double Sqrt( const double &x) 
{
	double         xHalf = 0.5 * x;
	int64_t  tmp   = 0x5FE6EB50C7B537AAl - ( *(int64_t*)&x >> 1);
	double         xRes  = * (double*)&tmp;

	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	xRes *= ( 1.5 - ( xHalf * xRes * xRes ) );
	return xRes * x;
}
*/
// }}}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int sx,sy,tx,ty;
    cin >> sx >> sy >> tx >> ty;
    rep(i,ty - sy){
        cout << 'U';
    }
    rep(i,tx - sx){
        cout << 'R';
    }
    cout << 'U';
    rep(i,tx - sx + 1){
        cout << 'L';
    }
    rep(i,ty - sy + 1){
        cout << 'D';
    }
    cout << 'R';
    rep(i,tx - sx){
        cout << 'R';
    }
    rep(i,ty - sy){
        cout << 'U';
    }
    cout << 'R';
    rep(i,ty - sy + 1){
        cout << 'D';
    }
    rep(i,tx - sx + 1){
        cout << 'L';
    }
    cout << "U\n";
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int s[10], c[10], n, m;
int main() {
    int i, ss, cc;
    scanf("%d%d", &n, &m);
    for(i = 1; i <= m; ++i) {
        scanf("%d%d", &ss, &cc);
        if(s[ss]) {
            if(c[ss] != cc) {
                printf("-1\n");
                return 0;
            }
        }
        if(ss == 1 && cc == 0 && n != 1) {
            printf("-1\n");
            return 0;
        }
        s[ss] = 1;
        c[ss] = cc;
    }
    for(i = 1; i <= n; ++i) {
        if(s[i]) printf("%d", c[i]);
        else if(i != 1 || n == 1) printf("0");
        else printf("1");
    }
    puts("");
    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<stdlib.h>
using namespace std;
long long a, b;
int main()
{
	cin >> a >> b;
	if(a > 0) cout << "Positive";
    else if(a == 0 || (a < 0 && b > 0)) cout << "Zero";
    else if((abs(b) - abs(a)) % 2 != 0) cout << "Positive";
    else cout << "Negative";
	return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;

class Main{
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final PrintWriter out = new PrintWriter(System.out);
    public static void main(String[] Args) throws IOException{
        while(true){
            final String str = br.readLine();
            if(str.equals("-")) break;
            final int m = Integer.parseInt(br.readLine());
            int h = 0;
            for(int i = 0; i<m; i++)
                h += Integer.parseInt(br.readLine());
            h %= str.length();
            out.println(str.substring(h)+str.substring(0, h));
        }
        out.flush();
    }
}

Measured memory_bytes: 24220
#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,M;
ll A[101010],B[101010];
pair<ll,int> C[101010];
vector<int> E[101010];
ll BS[101010];
ll Q[101010];
int did[101010];
template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<500000> uf;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>A[i]>>B[i];
		C[i]={max(A[i]-B[i],0LL),i};
		BS[i]=B[i];
	}
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	sort(C,C+N);
	FOR(i,N) {
		x=C[i].second;
		did[x]=1;
		vector<int> V;
		FORR(e,E[x]) if(did[e]==1) V.push_back(uf[e]);
		sort(ALL(V));
		V.erase(unique(ALL(V)),V.end());
		
		ll BSS=BS[x];
		FORR(e,V) BSS+=BS[e];
		
		Q[x]=C[i].first+BSS;
		FORR(e,V) Q[x]=min(Q[x],max(Q[e],C[i].first)+BSS-BS[e]);
		FORR(e,V) uf(e,x);
		Q[uf[x]]=Q[x];
		BS[uf[x]]=BSS;
		
	}
	cout<<Q[uf[0]]<<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: 15600
#include <bits/stdc++.h>

//Common
using namespace std;using f64 = double;using i64=long long;using u64=unsigned long long;
template<typename T> using Arr=vector<T>;template<typename T> using Func=function<T>;template<typename T> using Str=basic_string<T>;
#define hfor(v, s, e) for(int v=(s);(s)<=v&&v<(e);++v)//half-opened range
#define hfori(v, s, e) for(int v=(e)-1;(s)<=v&&v<(e);--v)//inversion
#define hforo(v, s, e) int v=(s);for(;(s)<=v&&v<(e);++v)//out declaration
#define hforoi(v, s, e) int v=(e)-1; for(;(s)<=v&&v<(e);--v)
#define cfor(v, s, e) hfor(v,(s),(e)+1)//closed range
#define cfori(v, s, e) hfori(v,(s),(e)+1)
#define cforo(v, s, e) hforo(v,(s),(e)+1)
#define cforoi(v, s, e) hforoi(v,(s),(e)+1)
#define rep(v,x) hfor(v,0,(x))
#define repi(v,x) hfori(v,0,(x))
#define repo(v,x) hforo(v,0,(x))
#define all(x) (x).begin(),(x).end()
#define pushb push_back
#define pushf push_front
#define popb pop_back
#define popf pop_front
#define empl emplace
#define emplb emplace_back
#define emplf emplace_front
#define fi first
#define se second
#define cxp constexpr
#define PQMIN(...) std::priority_queue<__VA_ARGS__,Arr<__VA_ARGS__>,greater<__VA_ARGS__>>
template<class... A>
auto ARR(auto n, A&&...a){
	if constexpr(sizeof...(a)==0) return n;
	else return vector(n,ARR(a...));
}

//Math
template<typename T> cxp T inf() { return numeric_limits<T>::max() / 2; }
template<typename T> inline T sq(T x){return x*x;}
cxp int lgc(int x){return 64-__builtin_clzll(x-1);}
cxp int lgf(int x){return 63-__builtin_clzll(x);}
int rd(int lb, int ub){static mt19937 rng(time(0)^i64(new int)); return uniform_int_distribution<int>(lb, ub-1)(rng);}
int rd(int ub=inf<int>()){return rd(0,ub);}
const f64 pi=acosl(-1), eps=1e-10;

//IO
template<typename T>ostream& operator<<(ostream& s, const Arr<T>& a) {for(auto i:a) cout<<i<<' '; return s;}
auto cinint(){i64 x;cin>>x;return x;}
auto cinchr(){char x;cin>>x;return x;}
auto cinints(int n){Arr<i64> a(n);for(auto&i:a)cin>>i;return a;}
#ifndef DEBUG
	//#pragma GCC optimize ("Ofast") //somtimes it become more slower
	auto __PRE_RUN__=(ios::sync_with_stdio(0), cin.tie(0), cout.tie(0),(cout<<fixed<<setprecision(11)), 0);
#endif

//Misc
int sz(const auto& x){return x.size();}
auto split(auto s, auto p){
	Arr<decltype(s)> ret;
	auto it1=s.begin();
	for(auto it2=it1; (it2 = find(it1,s.end(),p)) != s.end(); it1=it2+1)
		ret.pushb({it1, it2});
	ret.pushb({it1,s.end()});
	return ret;
}
template<typename T> T rev(const T& a){return {a.rbegin(),a.rend()};}
Arr<int> range(int n){ Arr<int> ret(n); rep(i,n)ret[i]=i; return ret; }
struct defer{ defer(auto f):f(f){} ~defer(){f();} function<void()> f; };
#define defer(x) auto _##__COUNTER__ = defer([&](){x;});
#define lam(expr, ...) [&](__VA_ARGS__){return expr;}
#define reduce accumulate

#define endl '\n'//not interactive?
#define int i64//MLE?
using pint = pair<int,int>;
using tint = tuple<int,int,int>;

signed main(){
	int z; cin>>z;
	cfor(n,1,z){
	int ans=0;
	for(int x=1;x*x<n;x++)
		for(int y=1;x*x+y*y+x*y<n;y++){
			int z=(-(x+y)+sqrt((x+y)*(x+y)-4*(x*x+y*y+x*y-n)))/2;
			if(x*x+y*y+z*z+x*y+y*z+z*x==n)
				ans++;
		}
	cout<<ans<<endl;
	}
	
	return 0;
}



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

#define ll long long
#define fr(i,l,r) for(i=(l);i<(r);i++)
#define min(p,q)((p)<(q)?(p):(q))

int main(void)
{
	//変数の宣言
	int x;
	//よく使う変数
	int i,j,k,l;
	int flag=0;
	int ans=0;
	int count=0;
	int temp,temp1,temp2;
	int max,min;
	int len;
	//データの読み込み
	
	scanf("%d",&x);
	
//	printf("nは%dです\n", n);
//	printf("データの読み込み終了\n");
	//実際の処理
	
//	printf("計算部分終了\n");
	//出力
	
	if(x==3||x==5||x==7){
		printf("YES");
	}else{
		printf("NO");
	}
	
	
//	printf("結果の出力終了\n");
	
	return 0;
	
}



Measured memory_bytes: 128
import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        long n, a, b;
        
        n = sc.nextLong();
        a = sc.nextLong();
        b = sc.nextLong();

        if (a > b){
            System.out.println(0);
            System.exit(0);
        }
      	else if(n==1 && a!=b){
            System.out.println(0);
            System.exit(0);
        }
      	else{
            long length = n - 2;
            System.out.println(length*(b-a)+1);
        }
    }
}


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

using namespace std;

int main()
{
    char x,y;
    cin>>x;
    int i = 1;

    while(i >= 0)
    {
        cin>>y;
        if(x != y)
        {
            break;
        }
        i--;

    }
    if(i >= 0)
    {
        cout<<"Yes";
    }
    else{
        cout<<"No";
    }

  
}

Measured memory_bytes: 256
unittest
{
	assert( [ "20" ].parse.expand.solve == 15800 );
	assert( [ "60" ].parse.expand.solve == 47200 );
}



import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = input.front.to!( long );
	return tuple( n );
}

auto solve( long n )
{
	return 800 * n - 200 * ( n / 15 );
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define F first
#define S second
#define int long long
#define ll long long
//#define int  unsigned long long
#define pb push_back
//#define double long double

using namespace std;
using namespace __gnu_pbds;
typedef  tree< int , null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int mod = 998244353;
const int N = 1200000;
vector <int> g[N];
int ans[N];
vector <int> a[2], v[3];
void dfs(int v, int p = -1, int h = 0){
    a[h % 2].pb(v);
    for (auto u: g[v]){
        if (u == p) continue;
        dfs(u, v, h + 1);
    }
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("input.txt", "r", stdin);
    int n;
    cin >> n;
    for (int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1);
    for (int i = 1; i <= n; i++){
        v[i % 3].pb(i);
    }
    if (a[0].size() > a[1].size()) swap(a[0], a[1]);
    if (v[0].size() >= a[0].size()){
        for (auto x: a[0]){
            ans[x] = v[0].back();
            v[0].pop_back();
        }
        for (int i = 0; i < 3; i++){
            while(!v[i].empty()){
                ans[a[1].back()] = v[i].back();
                v[i].pop_back();
                a[1].pop_back();
            }
        }
        for (int i = 1; i <= n; i++){
            cout << ans[i] << " ";
        }
        return 0;
    }
    while(!v[1].empty()){
        ans[a[1].back()] = v[1].back();
        v[1].pop_back();
        a[1].pop_back();
    }
    while(!v[2].empty()){
        ans[a[0].back()] = v[2].back();
        v[2].pop_back();
        a[0].pop_back();
    }
    for (int i = 0; i < 2; i++){
        while(!a[i].empty()){
            ans[a[i].back()] = v[0].back();
            v[0].pop_back();
            a[i].pop_back();
        }
    }
    for (int i = 1; i <= n; i++){
        cout << ans[i] << " ";
    }
}


Measured memory_bytes: 47980
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <string>
#include <iomanip>
using namespace std;
int main(){
	int n,k;
	double p[200000];
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>p[i];
		p[i]+=1;
		p[i]/=2;
	}
	double ans=0;
	double now=0;
	for(int i=0;i<k;i++){
		now+=p[i];
	}
	ans=max(ans,now);
	for(int i=k;i<n;i++){
		now-=p[i-k];
		now+=p[i];
		ans=max(ans,now);
	}
	cout<<fixed<<setprecision(12)<<ans<<endl;
	return 0;
}


Measured memory_bytes: 1792
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

a,b,c = LI()
if c - a - b >= 0:
    if 4 * a* b < (c - a- b) ** 2:
        ans = 1
    else:
        ans = 0
else:
    ans = 0
if ans:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 67436
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

/*const int MM = 4e8;
int mpos = 0;
char mem[MM];
inline void * operator new ( size_t n )
{
	char *res = mem + mpos;
	mpos += n;
	return (void *)res;
}
inline void operator delete ( void * ) { } */

#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)

const ld pi = acos(-1.0);
const ll INF = 1e18 + 239;
const int BIG = 1e9 + 239;
const ll MOD = 1e9 + 7;
const ll MOD2 = MOD * MOD;
const int M = 2 * 1e5 + 239;
const int N = 2 * 1e3 + 239;
const int X = 1e4 + 239;
const int L = 18;
const int T = (1 << 18);
const int two = 2;
const int th = 3;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int dp[M], n, a[M];

int main()
{   /*
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout); /**/
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int ans = 0;
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < n; i++)
    {
        if (dp[a[i] - 1] == -1) dp[a[i]] = 1;
        else dp[a[i]] = dp[a[i] - 1] + 1;
        ans = max(ans, dp[a[i]]);
    }
    cout << (n - ans);
    return 0;
}


Measured memory_bytes: 1920
#include <stdio.h>

#if 1
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif

#define MAX  40002
#define BASE 20000

int a[MAX];
int sum[MAX]; int sz;
int left[MAX];

int main()
{
	int i, j, k, x, h, s, ans;
	int c;

	h = BASE, ans = s = 0;
	for (x = 1; ; x++) {
		c = gc();
		if (c <= ' ') break;
		if (c == '\\') {//下っていくとき
			if (s > 0){ ans += s, sum[sz++] = s, s = 0;}
			a[--h] = x;
		} else if (c == '/') {//登っていくとき
			if (a[h] > 0) left[sz] = a[h], s += x-a[h];
			else if (s > 0) ans += s, sum[sz++] = s, s = 0;
			h++;
		}
	}
	if (s > 0) ans += s, sum[sz++] = s;

	printf("%d\n", ans);
	k = sz;
	i = sz-1; while (i > 0) {
		j = i-1; while (j >= 0 && left[j] > left[i]) {
			sum[i] += sum[j], sum[j] = 0, j--, k--;
		}
		i = j;
	}

	printf("%d", k);
	for (i = 0; i < sz; i++) if (sum[i] > 0) printf(" %d", sum[i]);
	putchar('\n');
	return 0;
}




Measured memory_bytes: 2108
#include<stdio.h>

int main(){
    int n,i,flg=0,j,k=0;

    scanf("%d",&n);
    int a[n];

    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    for(i=1;n>1 && i<n;i++){
        if(a[i-1]-a[i]==1){
            if(i<n-1 && a[i]-a[i+1]>0){
                flg=1;
                break;
            }else if(i<n-1 && a[i]-a[i+1]==0){
                j=i+1;
                while(j<n-1 && a[j]-a[j+1]==0 ){
                    j++;
                }if(j<n-1 && a[j]-a[j+1]>0){
                    flg=1;
                    break;
                }
            }
        }else if(a[i-1]-a[i]>1){
            flg=1;
            break;
        }
    }
    if(flg){
        printf("No\n");
    }else{
        printf("Yes\n");
    }
}

Measured memory_bytes: 512
#include "bits/stdc++.h"
using namespace std;

int main(void) {
    int X, Y, Z, K;
    cin >> X >> Y >> Z >> K;
    vector<long long> a(X);
    vector<long long> b(Y);
    vector<long long> c(Z);
    for (int i = 0; i < X; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < Y; ++i) {
        cin >> b[i];
    }
    for (int i = 0; i < Z; ++i) {
        cin >> c[i];
    }
    sort(a.rbegin(), a.rend());
    sort(b.rbegin(), b.rend());
    sort(c.rbegin(), c.rend());

    vector<long long> ans;

    for (int x = 0; x < X; ++x) {
        for (int y = 0; y < Y; ++y) {
            if ((x + 1)*(y + 1) > K) {
                continue;
            }
            for (int z = 0; z < Z; ++z) {
                if ((x + 1)*(y + 1)*(z + 1) > K) {
                    continue;
                }
                ans.push_back(a[x] + b[y] + c[z]);
            }
        }
    }
    sort(ans.rbegin(), ans.rend());
    for (long long i = 0; i < K; ++i) {
        cout << ans[i] << "\n";
    }
    return 0;
}

Measured memory_bytes: 1404
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
  let stdin = stdin();
  let stdin = stdin.lock();
  let token: String = stdin
    .bytes()
    .map(|c| c.expect("failed to read char") as char)
    .skip_while(|c| c.is_whitespace())
    .take_while(|c| !c.is_whitespace())
    .collect();
  token.parse().ok().expect("failed to parse token")
}

use std::cmp::{max, min};

fn main() {
  let a = read::<i32>();
  let b = read::<i32>();

  if a % b == 0 {
    println!("{}", 0);
  } else {
    println!("{}", 1);
  }
}



Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll INF = 100000000;
#define rep1(i, n) for (ll i=0; i<(n); i++) 
#define rep2(i, k, n) for (ll i=k; i<(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main() {
    string s;
    cin >> s;
    map<char, ll> check;
    rep1(i, 4){
        check[s[i]]++;
    }
    bool judge = true;
    rep1(i, 4){
        if (check[s[i]] != 2) judge = false;
    }
     
    if (judge) cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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

const ll INF = 1e9;
const ll MOD = 998244353;
const ll LINF = 1e18;

ll modpow(ll a, ll n) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % MOD;
    (a *= a) %= MOD;
    n >>= 1;
  }
  return res;
}

const ll maxf = 10000000;
ll fact[maxf+5];
ll ifact[maxf+5];

void fact_init(){
  fact[0] = 1;
  for(ll i=1; i<=maxf; i++) fact[i] = (fact[i-1] * i) % MOD;
  ifact[maxf]=modpow(fact[maxf],MOD-2);
  for(ll i=maxf; i>=1; i--) ifact[i-1] = (ifact[i] * i) % MOD;
}

ll comb(ll n, ll r){
  if(n<r || n<0 || r<0) return 0;
  if(fact[0] == 0) fact_init();
  return ((fact[n] * ifact[n-r]) % MOD * ifact[r]) % MOD;
}

ll naive_comb(ll n, ll r){
  ll res = 1;
  for (ll i = n; i > n - r; i--) res = res * i % MOD;
  for (ll i = 1; i <= r; i++) res = (res * modpow(i, MOD-2)) % MOD;
  return res;
}

// 0~kまでについて以下のことを考える
// 1) i組隣り合っている組を作る => n-1箇所のブロックの間からi箇所を選ぶ
// 2) 1でi組隣り合う部分を作ると、n個のブロックはn-i個の区間に分かれることになる
//    n-i個の区間に対する配色の仕方は、m*(m-1)^(n-k-1) 通りである
//    （最初の1区画は自由にm通り、残りの(n-k-1)区画については手前の1色を抜いたm-1通りから選択することになるため）

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  
  ll n,m,k; cin>>n>>m>>k;
  ll ans=0;
  rep(i,k+1){
    ll tmp=comb(n-1,i)*(m*modpow(m-1,n-i-1)%MOD)%MOD;
    // cout<<tmp<<endl;
    (ans+=tmp)%=MOD;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 159904
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char const *argv[])
{
	int n;
	int k , t;
	int a[10001];
	cin >> k >> t;
	for (int i = 0; i < t; ++i)
	{
		cin >> a[i];
	}

	sort(a,a+t);
	reverse(a,a+t);
	int l = 0, r = t-1;
	
	for (;;) {
		for (;l != r;) {
	//		cout << sum << " " << a[r] << endl;
			if (a[l] - a[r] < 0) {
				a[r] -= a[l];
				a[l] = 0;
				break;
			} else {
				a[l] -= a[r];
				a[r] = 0;
				r--;		
			}		
		}
		if (l == r)
		{
			break;
		}
		l++;
	}	

	cout << (a[l]? a[l]-1 : 0) << endl;


	return 0;
}

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


def readstr():
    return input().strip()


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


def main():
    x, y = readnums()
    '''
    x <= yかx > yか
    x, yの正負
    x, yの差
    x, y
    1, 3 2
    -1, 3 3
    1, -3 3
    -1, -3 4
    3, 1 4
    -3, 1 3
    3, -1 3
    -3, -1 2

    10, 0 11
    -10, 0 10
    0, 10 10
    0, -10 11
    '''
    ans = 0
    if x == 0 or y == 0:
        ans = abs(x - y) if x < 0 or y > 0 else abs(x - y) + 1
    elif (x >= 0 and y >= 0) or (x < 0 and y < 0):
        ans = y - x if x <= y else abs(abs(x) - abs(y)) + 2
    else:
        ans = abs(abs(y) - abs(x)) + 1
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,n) for(ll i=a;i<n;i++)
#define ALL(s) s.begin(),s.end()
#define P pair<ll,ll>
#define vl vector<ll>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvl vector<vector<ll>>
#define print(n) cout<<n<<endl
const int M=100111;
const int inf=1000000007;
const long long INF=1000000000000000007;
using ll=long long;
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};


int main(){
	
	string s;
	cin>>s;
	if(s[0]==s[1]||s[1]==s[2]||s[2]==s[3])
		print("Bad");
	else print("Good");
		
}	

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

#define MIN 1
#define MAX 36

struct Card{
  char s;
  char v;
};



void bubble(struct Card C[],int N){
  int i,j;
  struct Card t;
  for(i=0;i<=N-1;i++){
    for(j=N-1;j>=i;j--){
      if(C[j].v<C[j-1].v){
	t=C[j];
	C[j]=C[j-1];
	C[j-1]=t;
      }
    }
  }
}



void selection(struct Card C[],int N){
  int i,j,minj;
  struct Card t;
  for(i=0;i<=N-1;i++){
    minj=i;
    for(j=i;j<=N-1;j++){
      if(C[j].v<C[minj].v)
	minj=j;
    }
    t=C[i];
    C[i]=C[minj];
    C[minj]=t;
  }
}



void print(struct Card C[],int N){
  int i;
  for(i=0;i<=N-1;i++){
    if(i>0){
      printf(" ");
    }
    printf("%c%c",C[i].s,C[i].v);
  }
  printf("\n");
}



int isStable(struct Card C1[],struct Card C2[], int N){
  int i;
  for(i=0;i<=N-1;i++){
    if(C1[i].s!=C2[i].s)
      return 0;
  }
  return 1;
}




int main(){
  int i,j,N;
  struct Card C1[MAX],C2[MAX];
  char ch;
  
  scanf("%d",&N);
  if(N<MIN||N>MAX){
    exit(1);
  }
  for(i=0;i<=N-1;i++){
    scanf(" %c%c",&C1[i].s,&C1[i].v);
  }
  for(i=0;i<=N-1;i++){
    C2[i]=C1[i];
  }
  bubble(C1,N);
  selection(C2,N);
  
  print(C1,N);
  printf("Stable\n");
  print(C2,N);
  if(isStable(C1,C2,N)==1){
    printf("Stable\n");
  }
  else{
    printf("Not stable\n");
  }
  return 0;
}



Measured memory_bytes: 2144
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define ull unsigned long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define mp make_pair
#define pb push_back
#define all(v) v.begin(), v.end()
#define ub upper_bound
#define lb lower_bound
#define F first
#define S second

int main(){
    fastio;
    string s, t;
    cin  >> s >> t; 
    bool flag = true;
    for(int i=0; i<s.size(); i++){
        if(s[i] != t[i]) flag = false;
    }
    if(flag) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

Measured memory_bytes: 3652
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define mod 1000000007 //1e9+7
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 1001

void calc(int y,int m,int d){
  int ans = 0;

  if(y%3==0 || m%2){
    ans += 21-d;
  }else{
    ans += 20-d;
  }

  if(y%3==0){
    ans += (10-m)*20;
  }else{
    if(m%2){
      ans += (10-m)/2 * (19+20) + 19;
    }else{
      ans += (10-m)/2 * (19+20);
    }
  }

  for(int i=y+1;i<1000;i++){
    if(i%3==0) ans += 20*10;
    else ans += (20+19)*5;
  }
  
  printf("%d\n",ans);
}

int main(){
  int n,y,m,d;

  scanf("%d",&n);
  
  for(int i=0;i<n;i++){
    scanf("%d%d%d",&y,&m,&d);
    calc(y,m,d);
  }
  
  return 0;
}

Measured memory_bytes: 3200
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int gcd(int a, int b)
{
    if(b == 0) return a;
    return gcd(b, a%b);
}
int main()
{
    int n, mns = 0;
    long long s = 0;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
        if(a[i] < 0) ++mns;
        a[i] = abs(a[i]);
        s += a[i];
    }
    if(mns % 2 == 0){
        cout << s << endl;
        return 0;
    }
    sort(a.begin(), a.end());
    cout << s - a[0]*2 << endl;
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
 
typedef pair <int, int> pii;
typedef pair <long long, long long> pll;
#define pb push_back
#define ll long long
#define endl "\n"
#define min(a,b) (a < b ? a : b)
#define max(a,b) (a > b ? a : b)
#define fast_io() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
int main() 
{
    fast_io();
    int n; cin >> n;
    string s; cin >> s;
    int unique[n];
    set <char> st;
    for (int i = n-1; i >= 0; --i)
    {
        unique[i] = st.size(); 
        st.insert(s[i]);
    }
    int pos[n][10]; memset(pos,-1,sizeof(pos));
    for (int i = n-2; i >= 0; --i)
    {
        for (int j = 0; j < 10; ++j)
            pos[i][j] = pos[i+1][j];
        pos[i][s[i+1]-'0'] = i+1;
    }
    ll ans = 0;
    int f[10] = {0};
    for (int i = 0; i < n; ++i)
    {
        if (f[s[i]-'0']) continue;

        f[s[i]-'0'] = 1;
        for (int j = 0; j < 10; ++j)
        {
            int index = pos[i][j];
            if (index != -1)
                ans += unique[index];
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1664
D,N = (int(i) for i in input().split())

if D == 0:
    if N == 100:
        print(101)
    else:
        print(N)
elif D == 1:
    if N == 100:
        print(N*100+100)
    else:
        print(N*100)
elif D == 2:
    if N == 100:
        print(N*10000+10000)
    else:
        print(N*10000)

Measured memory_bytes: 3060
#include<iostream>
#include <algorithm>
#include <functional>
#include<vector>
#include<math.h>
#include <assert.h>
#include<bitset>
#include<string>
#include <deque>
#include<queue>
#include <iomanip>
#include<map>
#include <random>
#include<type_traits>
#include<stack>
#include <sstream> 
#include <limits>
#include <numeric>
#include<string.h>
#include<set>
#include <climits>
using namespace std;
typedef unsigned long long ull;
#define ll long long int
static const double PI = 3.141592653589793;
const ll INF = 100000000000000;
ll mod = 1000000007;
//typedef vector<int> V;
//typedef vector<V> VV;
//typedef vector<VV> VVV;

ll h[100005],c[100005];
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n;
	cin >> n;
	cout << n * (n -1) / 2 << endl;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS 
#include<stdio.h>
int main() {
	int k, s;
	scanf("%d%d", &k, &s);
	int a, b, c=0;
	int cnt=0;
	for (a = 0; a <= k; a++) {
		for (b = 0; b <= k; b++) {
			c = s - a - b;
			if (c >= 0 && c <= k) {
				cnt++;
			}
		}
	}
	printf("%d", cnt);


}

Measured memory_bytes: 128
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define size 200010
ll dp[4*size];
ll query(int s, int e, int qs, int qe, int idx)
{
  if(qs>e||qe<s)
    return 0;
  if(qs<=s&&qe>=e)
    return dp[idx];
  int mid=(s+e)/2;
  ll  a = query(s,mid,qs,qe,2*idx);
  ll  b = query(mid+1,e,qs,qe,2*idx+1);
  return max(a,b);
  
}
void update(int s,int e ,ll value ,int height,int idx)
{
    if(s>height||e<height) return;
  if(s==e){
    dp[idx]=value;
   // cout<<dp[idx]<<" "<<idx<<" ";
    return ;
  }
  int mid=(s+e)/2;
     update(s,mid,value,height,2*idx);
    update(mid+1,e,value,height,2*idx+1);
 
  dp[idx]=max(dp[2*idx],dp[2*idx+1]);
 // return ;
  
}
int main()
{
  int n;
  cin>>n;
  int i;
  vector<int> height(n,0),beauty(n,0);
  for(i=0;i<n;i++) cin>>height[i];
  for(i=0;i<n;i++) cin>>beauty[i];
  memset(dp,0,sizeof(dp));
  ll x=INT_MIN,a=0;
  for(i=0;i<n;i++)
  {
      a=query(0,n,0,height[i]-1,1);
     //x = max(x,a+beauty[i]);
    // cout<<a<<endl;
    update(0,n,beauty[i]+a, height[i],1);
  }
  //for(i=1;i<4*n;i++)
  //cout<<dp[i]<<" ";
  cout<<dp[1]<<endl;
}

Measured memory_bytes: 11176
n, q = (int(x) for x in input().split())
queries = [tuple(int(x) for x in input().split()) for _ in range(q)]
ans = (n - 2)**2
t1 = [n] * (n + 1)
t2 = [n] * (n + 1)
h, w = n, n
for t, x in queries:
    if t == 1:
        if x < w:
            tmp = h
            for i in range(x, w+1):
                t1[i] = h
            w = x
        else:
            tmp = t1[x]
        ans -= tmp - 2
    else:
        if x < h:
            tmp = w
            for i in range(x, h+1):
                t2[i] = w
            h = x
        else:
            tmp = t2[x]
        ans -= tmp - 2
print(ans)


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

using namespace std;

#define fRead(x)  freopen(x,"r",stdin)
#define fWrite(x) freopen (x,"w",stdout)

#define LL long long
#define ULL unsigned long long
#define ff first
#define ss second
#define pb push_back
#define INF 2e16
#define PI acos(-1.0)
#define mk make_pair

#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define min4(a,b,c,d) min(a,min(b,min(c,d)))
#define max4(a,b,c,d) max(a,max(b,max(c,d)))
#define SQR(a) ((a)*(a))
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define REP(i,b) for(int i=0;i<b;i++)
#define MEM(a,x) memset(a,x,sizeof(a))
#define ABS(x) ((x)<0?-(x):(x))

#define scanI(a) scanf("%d",&a)
#define scanI2(a,b) scanI(a) , scanI(b)
#define scanI3(a,b,c) scanI(a), scanI(b), scanI(c)
#define scanI4(a,b,c,d) scanI(a), scanI(b), scanI(c), scanI(d)

#define scanL(a) scanf("%I64d",&a)
#define scanL2(a,b) scanL(a) , scanL(b)
#define scanL3(a,b,c) scanL(a), scanL(b), scanL(c)
#define scanL4(a,b,c,d) scanL(a), scanL(b), scanL(c), scanL(d)

#define SORT(v) sort(v.begin(),v.end())
#define REV(v) reverse(v.begin(),v.end())

#define FastRead ios_base::sync_with_stdio(0);cin.tie(nullptr);

const int N = 55;
vector<pair<LL,LL>>g[N];
vector<LL>paths[N];

vector<LL>nodes;
LL found;
LL mask[N];

void dfs(LL node,LL pre,LL finish,LL id)
{
    if(found)return;
    if(node == finish){
        found = 1;
        paths[id] = nodes;
        return;
    }
    for(LL i = 0;i < g[node].size();i++){
        LL go = g[node][i].first;
        if(go == pre)continue;
        nodes.push_back(g[node][i].second);
        dfs(go,node,finish,id);
        nodes.pop_back();
    }
}
int main()
{
    LL n;
    cin >> n;
    for(LL i = 1;i < n;i++){
        LL a , b;
        cin >> a >> b;
        g[a].pb(mk(b,i));
        g[b].pb(mk(a,i));
    }
    LL m;
    cin >> m;

    for(LL i = 0;i < m;i++){
        LL u , v;
        cin >> u >> v;

        found = 0;
        nodes.clear();
        dfs(u,0,v,i);
    }
    for(LL i = 0;i < m;i++){
        LL M = 0;
        for(LL j : paths[i]){
            M = M | (1LL << (j - 1));
        }
        mask[i] = M;
    }
    LL ans = 0;
    for(LL i = 0;i < (1LL << m);i++){
        LL M = 0;
        for(LL j = 0;j < m;j++){
            if(i & (1LL << j)){
                M = M | mask[j];
            }
        }
        LL bits = __builtin_popcountll(M);
        LL ways = 1LL << (n - 1 - bits);
        if(__builtin_popcountll(i) % 2 == 0)ans += ways;
        else ans -= ways;
    }
//    assert(ans >= 0);
    cout << ans << "\n";
}



Measured memory_bytes: 384
// khodaya khodet komak kon
#include <bits/stdc++.h>
#define pb push_back
#define ers erase
#define ins insert
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x)  cerr << #x << " = " << x << endl
#define kill(x) return cout << x, 0;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#pragma GCC optimize ("Ofast")
using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef vector<pll> vpl;

const ld Pi = 3.14159265359;
const ll MOD = 1000 * 1000 * 1000 + 7;
const ll N = 5e5 + 10;
const ll INF = 1e18;
const ll LOG = 20;
ll n, a[N], q, Now, d, dp[N], koj[N];

int main(){
	IOS;
	cin >> n >> d;
	for (int i = 0; i < n; i++){
		cin >> a[i];
	}
	Now = d;
	//First = INF;
	koj[0] = abs(Now);
	for (int i = 0; i < n; i++){
		koj[i + 1] = min(koj[i], abs(koj[i] - a[i]));
	}
	dp[n] = 0;
	for (int i = n - 1; i >= 0; i--){
		if (dp[i + 1] * 2 + 1 >=  a[i]) dp[i] = dp[i + 1] + a[i];
		else dp[i] = dp[i + 1];
	}
	cin >> q;
	for (int i = 1; i <= q; i++){
		ll v;
		cin >> v;
		if (dp[v] < koj[v - 1]) cout << "YES\n";
		else cout << "NO\n";
	}
	
	return 0;
}






/*
     ,---,           ___                 ,--,
    '  .' \        ,--.'|_             ,--.'|                             ,--,
   /  ;    '.      |  | :,'            |  | :                           ,--.'|    ,---.        ,---,
  :  :       \     :  : ' :            :  : '                 .--.--.   |  |,    '   ,'\   ,-+-. /  |
  :  |   /\   \  .;__,'  /    ,--.--.  |  ' |     ,--.--.    /  /    '  `--'_   /   /   | ,--.'|'   |
  |  :  ' ;.   : |  |   |    /       \ '  | |    /       \  |  :  /`./  ,' ,'| .   ; ,. :|   |  ,"' |
  |  |  ;/  \   \:__,'| :   .--.  .-. ||  | :   .--.  .-. | |  :  ;_    '  | | '   | |: :|   | /  | |
  '  :  | \  \ ,'  '  : |__  \__\/: . .'  : |__  \__\/: . .  \  \    `. |  | : '   | .; :|   | |  | |
  |  |  '  '--'    |  | '.'| ," .--.; ||  | '.'| ," .--.; |   `----.   \'  : |_|   :    ||   | |  |/
  |  :  :          ;  :    ;/  /  ,.  |;  :    ;/  /  ,.  |  /  /`--'  /|  | '.'\   \  / |   | |--'
  |  | ,'          |  ,   /;  :   .'   \  ,   /;  :   .'   \'--'.     / ;  :    ;`----'  |   |/
  `--''             ---`-' |  ,     .-./---`-' |  ,     .-./  `--'---'  |  ,   /         '---'
                            `--`---'            `--`---'                 ---`-'
*/




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

#define SORT(v) sort(v.begin(),v.end())
#define si(n) scanf("%d",&n)
#define sii(n,m) scanf("%d %d",&n,&m)
#define sl(n) scanf("%lld",&n)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define ss(cad) scanf("%s",cad)
#define PB push_back
#define fst first
#define scn second
#define DBG(x) cerr << #x << " = " << (x) << endl; 
#define M 1000000007
#define N_MAX 100010

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vl;
typedef pair<int,int> pi;
typedef vector<pi> vp;

int main()
{
	int vec[3];
	sii(vec[0], vec[1]);
	si(vec[2]);
	sort(vec, vec+3);
	if(vec[0] == vec[1] && vec[1]!= vec[2])
		printf("Yes\n");
	else if(vec[1] == vec[2] && vec[1]!= vec[0])
		printf("Yes\n");
	else
		printf("No\n");
    return 0;
}


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

int main(){
  int a,b,c;
 
  cin >> a >> b >> c;
  
  if(c - (a - b) > 0){
  	cout << c - (a - b) << endl;
  } else{
    cout << 0 << endl;
  }
}

Measured memory_bytes: 256
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, c = map(int, readline().split())
    l = 2 * (10 ** 5) + 1
    cum = [0] * l
    used = [[False] * l for _ in range(c + 1)]

    for i in range(n):
        s, t, c = map(int, readline().split())
        if used[c][2 * s]:
            cum[2 * s] += 1
        else:
            cum[2 * s - 1] += 1
            used[c][2 * s] = True

        if used[c][2 * t]:
            cum[2 * t - 1] -= 1
        else:
            cum[2 * t] -= 1
            used[c][2 * t] = True

    ans = 0
    cur = 0
    for x in cum:
        cur += x
        ans = max(ans, cur)

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 123812
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <cmath>
using namespace std;
#define MOD 1000000007
#define INF 1<<30
#define LINF (ll)1<<62
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> P;
typedef vector<pair<ll, ll>> vpl;
const int mod = 1e9 + 7;

int main(){
    vl v(9,0);
    ll n; cin >> n;
    rep(i,n){
        ll a; cin >> a;
        ll t = a/400<=7 ? a/400 : 8;
        v[t]++;
    }
    ll ans = 0;
    rep(i,8) if(v[i]>0) ans++;
    ll mn = ans>0 ? ans : 1;
    ll mx = ans + v[8];
    cout << mn << " " << mx << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string.h>
using namespace std;
int main(){
	char c[200]={0},mojiretu[100]={0};
	int i,a,count=0;
	cin>>c>>mojiretu;
	for(i=0;c[i]!='\0';i++){}
	for(a=i;a<i*2;a++){
		c[a]=c[a-i];
	}
	if(strstr(c,mojiretu)!=NULL){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}		
	return 0;
}

Measured memory_bytes: 1144