akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
#include <string>
#include<vector>
#include <utility>
#include <cstdio>
using namespace std;
typedef long long ll;

int main()
{
    ll n;
    cin>>n;
    ll a[n],b[n],c[n];
    for(ll i=0;i<n;i++){
        cin>>a[i];
        cin>>b[i];
        cin>>c[i];
    }
    for(ll i=1;i<n;i++){
        a[i]+=max(b[i-1],c[i-1]);
        b[i]+=max(a[i-1],c[i-1]);
        c[i]+=max(a[i-1],b[i-1]);
    }
    cout<<max(a[n-1],max(b[n-1],c[n-1]));
}




Measured memory_bytes: 2560
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner tan = new Scanner(System.in);
        while(tan.hasNext()){
            int k,x;
            k=tan.nextInt();
            x=tan.nextInt();
            if(500*k>=x)
                System.out.println("Yes");
            else
                System.out.println("No");
        }
    }
}


Measured memory_bytes: 21460
#include <stdio.h>
#include <string.h>
int a, b, r[101];
int main() {
	while (~scanf("%d%d", &a, &b)) {
		if (a == 0 && b == 0) {
			bool flag = r[1] % 2 == 1 && r[2] % 2 == 1;
			for (int i = 3; i <= 100; i++) {
				if (r[i] % 2 != 0) {
					flag = false;
				}
			}
			printf("%s\n", flag ? "OK" : "NG");
			memset(r, 0, sizeof(r));
		}
		else {
			r[a]++; r[b]++;
		}
	}
	return 0;
}

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


int main()
{
	int n,k;
	scanf("%d %d",&n,&k);
	
	vector<int> v(n+1);
	
	for(int i=1;i<=n;i++)
	scanf("%d",&v[i]);
	
	vector<int> dp(n+1,INT32_MAX);
	
	dp[1] = 0;
    dp[2] = fabs(v[1]-v[2]);
	
	for(int i=3;i<=n;i++)
	{
	    for(int j=1;j<=k;j++)
	    {
	        if(i-j<1)
	        break;
	        
	        int dx = fabs(v[i]-v[i-j]);
	        dp[i] =min(dp[i],dp[i-j]+dx);
	    }
	}
	printf("%d\n",dp[n]);
	
	return 0;
}

Measured memory_bytes: 4020
#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <complex>
#include <string.h>
#include <numeric>
using namespace std;

#define int long long
#define reps(i,s,n) for(int (i)=(s);(i)<(n);++(i))
#define rep(i,n) reps(i,0,n)
#define rept(i,n) rep(i,(n)+1)
#define repst(i,s,n) reps(i,s,(n)+1)
#define reprt(i,n,t) for(int (i)=(n);(i)>=(t);--(i))
#define repr(i,n) reprt(i,n,0)
#define each(i,v) for(auto &(i):(v))
#define eachr(i,v) for(auto &(i)=(v).rbegin();(i)!=(v).rend();(i)++)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define tmax(x,y,z) max(x,max(y,z))
#define tmin(x,y,z) min(x,min(y,z))
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define ln '\n'
#define bln(i,n) (((i)==(n)-1)?'\n':' ')
#define dbg(x) cout<<#x" = "<<(x)<<ln<<flush
#define dbga(x,n) {cout<<#x" : ";for(int (i)=0;i<(n);++i){cout<<((x)[i])<<(i==((n)-1)?'\n':' ')<<flush;}}
#define zero(a) memset(a,0,sizeof(a))
#define unq(a) sort(all(a)),a.erase(unique(all(a)),a.end())
#define endl "\n"

//typedef complex<double> P;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vst;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vector<int> > mat;

const ll inf = (ll)1e9+10;
const ll linf = (ll)1e18+10;
const ll mod = (ll)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};
const double eps = 1e-10;

ll mop(ll a,ll b,ll m=mod) {ll r=1;a%=m;for(;b;b>>=1){if(b&1)r=r*a%m;a=a*a%m;}return r;}
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
bool ool(int x,int y,int h,int w) {return((x<0)||(h<=x)||(y<0)||(w<=y));}
bool deq(double a,double b) {return abs(a-b)<eps;}

struct oreno_initializer {
	oreno_initializer() {
		cin.tie(0);
		ios::sync_with_stdio(0);
	}
} oreno_initializer;



int a;
set<int> s;

signed main() {
	cin >> a;
	s.insert(a);
	reps(i,2,1001001) {
		if (a%2) a = a*3+1;
		else a = a/2;
		if (s.count(a)) return cout << i << endl, 0;
		s.insert(a);
	}
}

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

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

  if (S[5] == '0' && S[6] - '0' <= 4)
    cout << "Heisei" << endl;
  else
    cout << "TBD" << endl;
  return 0;
}

Measured memory_bytes: 3552
x=int(input())
if x<=599:
  print(8)
elif x<=799:
  print(7)
elif x<=999:
  print(6)
elif x<=1199:
  print(5)
elif x<=1399:
  print(4)
elif x<=1599:
  print(3)
elif x<=1799:
  print(2)
else:
  print(1)

Measured memory_bytes: 9112
N  = int(input())
A=[0]*N
min_value = float('inf')
for i in range(N):
    A[i]= int(input())
    if(A[i]%10!=0):
        min_value=min(min_value,A[i])
A.sort()
sum_A=sum(A)
if(sum_A%10!=0):
    print(sum_A)
else:
    if(min_value!=float('inf')):
        print(sum_A-min_value)
    else:
        print(0)

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

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	int ans;
	ans = (n - 1) / (k - 1);
	if ((n - 1) % (k - 1) != 0)
		ans++;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 640
#include<math.h>
#include<map>
#include<iostream>
#include <algorithm>
#include <string>
#include<vector>
#include<array>
#include<tuple>
#include<queue>
#include<stack>
#include<iomanip>
#include<bitset>
#include <list>
#include<numeric>
//AtCoderC++.cpp

using namespace std;

inline int ceiling(int n, int d) {
	return n % d == 0 ? n / d : n / d + 1;
}

int main() {
	int h, w; cin >> h >> w;
	string s;
	for (size_t i = 0; i < h; i++) {
		cin >> s;
		cout << s << endl << s << endl;
	}
}


Measured memory_bytes: 256
#include<iostream>

#define inf 1000000000

using namespace std;


int n,m;
int C[100][100];

int prim(){
	int from[100],now[100],visit[100];
	int ans=0;
	
	for(int i=0;i<100;i++){
		from[i]=visit[i]=0;
		now[i]=inf;
	}
	
	now[0]=0;
	from[0]=-1;
	
	while(1){
		int mini=inf,mino;
		for(int i=0;i<n;i++){
			if(visit[i]==1){
				continue;
			}
			if(mini>now[i]){
				mini=now[i];
				mino=i;
			}
		}
		
		if(mini==inf){
			break;
		}
		visit[mino]=1;
		
		if(from[mino]!=-1)
		ans+=C[mino][from[mino]];
		
		for(int i=0;i<n;i++){
			if(C[mino][i]==inf || visit[i]==1){
				continue;
			}
			if(now[i]>C[mino][i]){
				now[i]=C[mino][i];
				from[i]=mino;
			}
		}
	}
	
	return ans;
}

int main(){
	while(1){
		cin>>n>>m;
		if(n==0)break;
		for(int i=0;i<100;i++){
			for(int j=0;j<100;j++){
				C[i][j]=inf;
			}
		}
		
		for(int i=0;i<m;i++){
			int a,b,c;
			cin>>a>>b>>c;
			C[a][b]=C[b][a]=c;
		}
		
		printf("%d\n",prim());
	}
}

Measured memory_bytes: 0
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.charset.StandardCharsets;
import java.util.*;
 
public class Main {
 
	public static void main(String[] args) throws IOException {
		InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
		BufferedReader in = new BufferedReader(reader);
		long MOD = 1000000007L;
 
		String[] tokens = in.readLine().split(" ");
		int N = Integer.parseInt(tokens[0]);
		int M = Integer.parseInt(tokens[1]);
 
		boolean[] statuses = new boolean[N + 1];
		Arrays.fill(statuses, true);
 
		for (int i = 0; i < M; ++i) {
			int index = Integer.parseInt(in.readLine());
			statuses[index] = false;
		}
 
		long[] counts = new long[N + 1];
		Arrays.fill(counts, 0);
		counts[0] = 1;
		if (statuses[1]) {
			counts[1] = 1;
		} else {
			counts[1] = 0;
		}
 
		for (int i = 2; i <= N; ++i) {
			if (statuses[i]) {
				counts[i] = (counts[i - 2] + counts[i - 1]) % MOD;
			} else {
				counts[i] = 0;
			}
		}
		System.out.println(counts[N]);
	}
}

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

int main() {
	int n,m,a[100][100],b[100];
	int ans[100]={0};
	
	cin>>n>>m;
	
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>a[i][j];
		}
	}
	for(int i=0;i<m;i++){
		cin>>b[i];
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			ans[i]+=a[i][j]*b[j];
		}
		cout<<ans[i]<<endl;
	}
	
	return 0;
}

Measured memory_bytes: 1200
MOD = 1000000007
N = int(input())
A = [int(i) for i in input().split()]
count = [0]*N
dp = [0]*N
if A[0] != 0:
    print(0)
    exit()
dp[0] = 3
count[0] += 1
for i, a in enumerate(A[1:]):
    if a == 0:
        dp[i+1] = dp[i]*(3-count[a])
    elif count[a] >= count[a-1]:
        print(0)
        exit()
    else:
        dp[i+1] = dp[i]*(count[a-1]-count[a])
    count[a] += 1
    dp[i+1] %= MOD
print(dp[-1])


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

using namespace std;

using i64 = int64_t;
using P = pair<i64, i64>;

struct edge {
    i64 from, to, cost;
    edge(i64 from, i64 to) : from(from), to(to), cost(1) {}
    edge(i64 from, i64 to, i64 cost) : from(from), to(to), cost(cost) {}
};
using Graph = vector<vector<edge>>;

constexpr i64 INF = std::numeric_limits<i64>::max();
constexpr i64 SINF = std::numeric_limits<i64>::max() / 10;
const i64 dx[4] = { 0,1,0,-1 }, dy[4] = { -1,0,1,0 };
//const i64 dx[5] = {-1,0,0,0,1}, dy[5] = {0,-1,0,1,0};
//const i64 dx[8] = {-1,0,1,1,1,0,-1,-1}, dy[8] = {1,1,1,0,-1,-1,-1,0};
//const i64 dx[9] = {-1,0,1,1,1,0,-1,-1,0}, dy[9] = {1,1,1,0,-1,-1,-1,0,0};

#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)

// http://beet-aizu.hatenablog.com/entry/2018/04/08/145516
template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }

template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
    for (auto& e : t) fill_v(e, v);
}

struct IoSetup {
    IoSetup() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
        cerr << fixed << setprecision(10);
    }
} iosetup;

int main(){
    i64 n;
    cin >> n;
    vector<i64> p(n);
    rep(i, n) cin >> p[i];
    i64 ans = 0;
    rep(i, 1, 101){
        i64 cnt = 0;
        rep(j, n) if(p[j] >= i) ++cnt;
        if(cnt >= i) ans = i;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3120
#include <bits/stdc++.h>
using namespace std;
 
#define debug(P) cout<<#P<<" = "<<P<<endl;
 
typedef long long ll;
typedef long double ld;
 
const int mod = 1e9+7;
 
 
 
 
int main() {
	//freopen("input.txt","r",stdin);
	
	ll x;
	cin>>x;

	ll p = 100;

	int years = 0;

	while(p < x){
		p = p + p/100;
		++years;
	}

	cout<< years << endl;
 
}

Measured memory_bytes: 3624
#include<stdio.h>
int main()
{
  int X;
  scanf("%d",&X);
  if(X>=400 && X<=599) printf("8");
  	else if(X>=600 && X<=799) printf("7");
  		else if(X>=800 && X<=999) printf("6");
  			else if(X>=1000 && X<=1199) printf("5");
    			else if(X>=1200 && X<=1399) printf("4");
     			 	else if(X>=1400 && X<=1599) printf("3");
                      else if(X>=1600 && X<=1799) printf("2");
                        else if(X>=1800 && X<=1999) printf("1");
  
  return 0;
}

Measured memory_bytes: 1648
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,double> P;
int main(){
  int n,m,p,a,b;
  while(cin>>n>>m>>p>>a>>b,n){
    a--,b--;

    int x,y;
    double t[8],tp;
    vector<P> e[31];
    for(int i=0;i<n;i++)cin>>t[i];
    while(p--){
      cin>>x>>y>>tp;
      x--,y--;
      e[x].push_back(P(y,tp)),e[y].push_back(P(x,tp));
    }

    double dp[1<<8][30];
    for(int i=0;i<1<<n;i++)
	for(int j=0;j<m;j++)dp[i][j]=1e4;
    dp[0][a]=0;

    for(int i=0;i<1<<n;i++)
      for(int j=0;j<m;j++)
	for(int k=0;k<n;k++)
	  if(!(i&1<<k))
	    for(int l=0;l<e[j].size();l++)
	      dp[i+(1<<k)][e[j][l].first]
	 =min(dp[i+(1<<k)][e[j][l].first],dp[i][j]+e[j][l].second/t[k]);

    double ans=1e4;
    for(int i=0;i<1<<n;i++)ans=min(ans,dp[i][b]);
    if(ans==1e4)cout<<"Impossible"<<endl;
    else cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 3280
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		String c[] = new String[a];
		char d[][] = new char[a][b];
		boolean f1[] = new boolean[a];
		boolean f2[] = new boolean[b];
		
		
		for (int i=0; i<a; i++){
			c[i] = sc.next();
			for (int j=0; j<b; j++){
				d[i][j] = c[i].charAt(j);
			}
		}
		
		for (int i=0; i<a; i++){
			f1[i] = false;
			for (int j=0; j<b; j++){
				if (d[i][j] != '.'){
					f1[i] = true;
				}
			}
		}
//		for (int i=0; i<f1.length; i++){
//			System.out.print(f1[i]+",");
//		}
//		System.out.println("");
		
		
		boolean temp = false;
		for (int j=0; j<b; j++){
			f2[j] = false;
			temp = false;
			for (int i=0; i<a; i++){
//				System.out.print(d[i][j]);
				if (d[i][j] != '.'){
					temp = true;
//					System.out.print("yes");
				}
			}
			if (temp){
//				System.out.print("aaa");
				f2[j] = true;
			}
//			System.out.println("");
//			System.out.println("-----------");
		}
//		for (int i=0; i<f2.length; i++){
//			System.out.print(f2[i]+",");
//		}
//		System.out.println("");

		for (int i=0; i<a; i++){
			if (!f1[i]){
				continue;
			}
			for (int j=0; j<b; j++){
				if (!f2[j]){
					continue;
				}
				System.out.print(d[i][j]);
			}
			System.out.println("");
		}
		
		
		
//		System.out.println(a-b+1);
		
		
		
		
	}

}


Measured memory_bytes: 25812
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define vv vector<ll>
#define pb push_back
#define rep(i,a,n) for(ll i=a;i<(long long)n;++i)
#define repr(i,n,a) for(ll i=n;i>(long long)a;--i)
#define fe(it,v) for(auto it:v)
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mod 1000001
using namespace std;

void solve(){
	double d,t,s;
	cin>>d>>t>>s;
	if(d/s <=t ) cout<<"Yes";
	else cout<<"No";

}

int main()
{
	// ll t;
	// cin>>t;
	// while(t--){
		solve();
		// cout<<endl;
// }
return 0 ;
}


Measured memory_bytes: 3720
n, _m, c = gets.strip.split.map(&:to_i)
b = gets.strip.split.map(&:to_i)

count = 0
n.times do
  a = gets.strip.split.map(&:to_i)
  sum = 0
  a.size.times do |j|
    sum += a[j] * b[j]
  end
  count += 1 if sum + c > 0
end

puts count

Measured memory_bytes: 1788
/*  -*- coding: utf-8 -*-
 *
 * a.cc: A - Don't be late
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

/* typedef */

/* global variables */

/* subroutines */

/* main */

int main() {
  int d, t, s;
  scanf("%d%d%d", &d, &t, &s);

  if (d <= t * s) puts("Yes");
  else puts("No");
  return 0;
}


Measured memory_bytes: 3768
#include <iostream>
#include <string>
using namespace std;
int main(void){
 unsigned long long n,t,a,b,ans=0;
 cin>>n>>t>>a;
 for(int i=0;i<n-1;i++){
     cin>>b;
     if(b-a>t){
         ans+=t;
     }else ans+=(b-a);
     a=b;
 }
 cout<<ans+t;
}

Measured memory_bytes: 256
for _ in range(int(input())):
    n, k = map(int, input().split())
    xs = list(map(int, input().split()))
    rs = sorted([xs[i + 1] - xs[i]for i in range(n - 1)])
    if k >= n:
        print(0)
    else:
        print(sum(rs[:n - k]))

Measured memory_bytes: 23860
#include <stdio.h>
typedef struct {/*parent,left child ,right sibling*/
int p,l,r;
} node;
node T[27];
void Preorder(int );
void Inorder(int );
void Postorder(int );
int main()
{
int n,i,id,l,r;
scanf("%d",&n);
 
for(i=0;i<n;i++)
{
T[i].p = T[i].l = T[i].r = -1;
}
 
for(i=0;i<n;i++)
{
scanf("%d%d%d",&id,&l,&r);
T[id].l = l;
T[id].r = r;
T[l].p = id;
T[r].p = id;
}
 
for(i=0;i<n;i++) if(T[i].p == -1) break;
printf("Preorder\n");
Preorder(i);
printf("\n");
printf("Inorder\n");
Inorder(i);
printf("\n");
printf("Postorder\n");
Postorder(i);
printf("\n");
return 0;
}

void Preorder(int id)
{
printf(" %d",id);
if(id != -1)
{
if(T[id].l != -1) Preorder(T[id].l);
if(T[id].r != -1) Preorder(T[id].r);
}
}

void Inorder(int id)
{
if(id != -1)
{
if(T[id].l != -1) Inorder(T[id].l);
printf(" %d",id);
if (T[id].r != -1) Inorder(T[id].r);
}
}
void Postorder(int id)
{
if(id != -1)
{
if(T[id].l != -1) Postorder(T[id].l);
if (T[id].r != -1) Postorder(T[id].r);
}
printf(" %d",id);
}

Measured memory_bytes: 616
[<AutoOpen>]
module Program

open System

let read f = stdin.ReadLine() |> f
let reada f = stdin.ReadLine().Split() |> Array.map f
let reads f = stdin.ReadLine().Split() |> Array.toList |> List.map f

[<EntryPoint>]
let main _ =
    let N = read int
    if N % 2 = 0 then
        N / 2 - 1
    else
        N / 2
    |> printfn "%i"
    0

Measured memory_bytes: 14040
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <set>
#include <iomanip>
#include <stdio.h>
#include <sstream>
#include <bits/stdc++.h>
using namespace std;
int main(void){
  string s;
  cin>>s;
  long long int ans=s.size();
  long long int nows=0;
  for(long long int i=0; i<s.size(); i++){
    if(s[i]=='S'){
      nows++;
    }
    if(s[i]=='T'){
      if(nows>0){
        nows--;
        ans-=2;
      }
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3724
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
const int N = 3e5+5;
int a[N];
void solve(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=k+1;i<=n;i++){
        if(a[i]>a[i-k])cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
//    cin>>t;
    while(t--)solve();
    return 0;
}


Measured memory_bytes: 4432
#include<iostream>
using namespace std;
int main(){
  int d1,d2,d3;
  while(cin >> d1 >> d2 >> d3){
    int i,j,k=0;
    for(i=1;i<=10;i++){
      if(i==d1||i==d2||i==d3) continue;
      if(d1+d2+i<=20) k++;
    }
    //cout << k << endl;
    if(k*2>7) cout << "YES" << endl;
    else cout << "NO" << endl;
  }
  return 0;
}

Measured memory_bytes: 1152
k=input()
n=len(k)
d=int(input())
mod=10**9+7
dp=[[[0]*2 for _ in range(d)] for i in range(n)]
for num in range(int(k[0])+1):
    if num==int(k[0]):
        dp[0][num%d][0]+=1
    else:
        dp[0][num%d][1]+=1
for i in range(1,n):
    num=int(k[i])
    for l in range(10):
        for j in range(d):
            if l<num:
                dp[i][(j+l)%d][1]+=dp[i-1][j][0]
            elif l==num:
                dp[i][(j+l)%d][0]+=dp[i-1][j][0]
            dp[i][(j+l)%d][1]+=dp[i-1][j][1]
            dp[i][(j+l)%d][1]%=mod
            dp[i][(j+l)%d][0]%=mod
print((sum(dp[n-1][0])-1+mod)%mod)

Measured memory_bytes: 162048
N=int(input())
x=list(map(int,input().split()))

count=0
for i in range(N-2):
    if x[i]<=x[i+1] and x[i+1]<=x[i+2]:
        count+=1
    elif x[i]>=x[i+1] and x[i+1]>=x[i+2]:
        count+=1
print(count)


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

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    int n;
    cin >> n;
    if (n == 1)
    {
        cout << "Yes" << endl << "2" << endl;
        cout << "1 1" << endl;
        cout << "1 1";
        return 0;
    }
    for (int il = 2; il <= n; ++il)
    {
        if ((1 + (il - 1)) * (il - 1) / 2 == n)
        {
            cout << "Yes" << endl << il << endl;
            vector< vector<int> > a(il);
            int nr = 1;
            for (int i = 0; i < il - 1; ++i)
            {
                for (int j = i + 1; j < il; ++j)
                {
                    a[i].push_back(nr);
                    a[j].push_back(nr);
                    ++nr;
                }
            }
            for (int i = 0; i < il; ++i)
            {
                cout << a[i].size() << " ";
                for (int j = 0; j < a[i].size(); ++j)
                    cout << a[i][j] << " ";
                cout << endl;
            }
            return 0;
        }
    }
    cout << "No";
    return 0;
}


Measured memory_bytes: 2304
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <limits>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <functional>

using namespace std;

using ll = long long;
using ui = unsigned int;
const ll MOD = 1000000007;
const ll INF = 9223372036854775807;

//D
//mod. m �ł� a �̋t�� a^{-1} ���v�Z����
//�g�p(num1 / num2) % m : (num1 * modinv(num2, m)) % m
ll modinv(ll a, ll m) {
	ll b = m, u = 1, v = 0;
	while (b) {
		ll t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}


//�g�ݍ��킹C��mod�������l�����߂�
ll calcCombinationMOD(ll n, ll r, ll mod) {
	ll num = 1;
	for (ll i = 1; i <= r; i++) {
		num = num * (n - i + 1);
		num = num % mod;
		num = (num * modinv(i, mod)) % mod;
	}
	return num;
}

int main() {
	ll X;
	scanf("%lld", &X);
	ll Y;
	scanf("%lld", &Y);

	if ((X + Y) % 3 != 0) {
		printf("0\n");
		return 0;
	}

	ll M = (X + Y) / 3;
	ll Mx = X - M;
	ll My = Y - M;

	if (Mx < 0 || My < 0) {
		printf("0\n");
		return 0;
	}
 
	ll result = calcCombinationMOD(Mx + My, Mx, MOD);

	printf("%lld\n", result);
}

//C
/*
struct LLPoint {
	ll x = 0;
	ll y = 0;
	LLPoint() {}
	LLPoint(ll x, ll y) {
		this->x = x;
		this->y = y;
	}
};

// nPn�̏���ɑ΂��ď��������s����
void foreach_permutation(int n, std::function<void(int *)> f) {
	int *indexes = new int[n];
	for (int i = 0; i < n; i++) indexes[i] = i;
	do {
		f(indexes);
	} while (std::next_permutation(indexes, indexes + n));
	delete[] indexes;
}

ll N;
double sum = 0;
ll c = 0;
vector<LLPoint> P;

int main() {
	scanf("%lld", &N);
	P.resize(N);
	for (ll i = 0; i < N; i++) {
		scanf("%lld %lld", &P[i].x, &P[i].y);
	}

	//���s��
	foreach_permutation(N, [](int *indexes) {
		//indexes[0] ~ indexes[N - 1]
		for (ll i = 0; i < N - 1; i++) {
			//i -> i+1
			ll sx = P[indexes[i]].x - P[indexes[i + 1]].x;
			ll sy = P[indexes[i]].y - P[indexes[i + 1]].y;
			double d = sqrt((double)(sx * sx) + (double)(sy * sy));
			sum += d;
		}
		c++;
	});

	double result = sum / (double)c;

	printf("%0.10f\n", result);
}
*/

//B
/*
int main() {
	ll N;
	scanf("%lld", &N);
	char S[220];
	scanf("%s", &S);

	bool result = true;

	if (N % 2 == 0) {
		ll half = N / 2;
		for (ll i = 0; i < half; i++) {
			if (S[i] != S[i + half]) {
				result = false;
				break;
			}
		}
	}
	else {
		result = false;
	}

	if (result) {
		printf("Yes\n");
	}
	else {
		printf("No\n");
	}
}
*/

//A
/*
int main() {
	ll r;
	scanf("%lld", &r);

	ll result = r * r;

	printf("%lld\n", result);
}
*/



Measured memory_bytes: 384
#include <iostream>
using namespace std;
int main() {
  int a[5];
  int k;
  int max = 0, min = 100000;
  for(int i = 0; i < 5; i++) {
    cin >> a[i];
    if(max < a[i]) max = a[i];
    if(min > a[i]) min = a[i];
  }
  cin >> k;
  if(k < max - min) cout << ":(" << endl;
  else cout << "Yay!" << endl;
  return 0;
}


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


int main(void){
char s[100];
int sum=0;
scanf("%s",s);
for(int i=0;s[i]!='\0';i++){
sum=sum+(s[i]-'0');
}
int sum2=atoi(s);
if(sum2%sum==0){printf("Yes\n");}
else{printf("No\n");}
}


Measured memory_bytes: 128
//============================================================================
// Name        : DPTest.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <queue>
using namespace std;

int H,W;
int M[1002][1002]={};
int dp[1002][1002]={};
int dp2[1002][1002]={};
typedef pair<int,int> P;
const int INF=1000000000;

int main() {
	cin>>H>>W;
	for(int i=1;i<H+1;i++){
		for(int j=1;j<W+1;j++){
			cin>>M[i][j];
		}
	}
	for(int i=0;i<H+2;i++){
		M[i][0]=INF;
		M[i][W+1]=INF;
	}
	for(int i=0;i<W+2;i++){
		M[0][i]=INF;
		M[H+1][i]=INF;
	}
	queue<P> que;
	int x1,y1;
	for(int i=1;i<H+1;i++){
		for(int j=1;j<W+1;j++){
			if((M[i][j]<M[i-1][j]&&M[i][j]<M[i+1][j])&&(M[i][j]<M[i][j-1]&&M[i][j]<M[i][j+1])){
				//init
				fill(dp[0],dp[1002],0);
				que.push(P(i,j));
				while(!que.empty()){
					P p1=que.front();que.pop();
					x1=p1.first;
					y1=p1.second;
					if(dp[x1][y1]>0||dp2[x1][y1]>1)continue;
					dp[x1][y1]=1;
					dp2[x1][y1]+=1;
					if(M[x1-1][y1]>M[x1][y1]&&x1>1)que.push(P(x1-1,y1));
					if(M[x1+1][y1]>M[x1][y1]&&x1<H)que.push(P(x1+1,y1));
					if(M[x1][y1-1]>M[x1][y1]&&y1>1)que.push(P(x1,y1-1));
					if(M[x1][y1+1]>M[x1][y1]&&y1<W)que.push(P(x1,y1+1));
				}
			}
		}
	}
	int R=0;
	for(int i=1;i<H+1;i++){
		for(int j=1;j<W+1;j++){
			if(dp2[i][j]>1)R++;
		}
	}
	cout<<R<<endl;
	return 0;
}

Measured memory_bytes: 14840
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    e = collections.defaultdict(set)
    for i in range(n-1):
        a,b = LI()
        e[a].add(b)
        e[b].add(a)

    def f(i,c):
        r = 0
        for j in e[i]:
            if j == c:
                continue
            t = f(j,i)
            r ^= t
        return r + 1

    if f(1,-1) == 1:
        return 'Bob'
    return 'Alice'


print(main())



Measured memory_bytes: 148816
#include <stdio.h>

int main(){
  int N,D,X[20][20],S=0;
  scanf("%d %d",&N,&D);
  for(int i=1;i<=N;i++){
    for(int j=1;j<=D;j++){
      scanf("%d",&X[i][j]);
    }
  }
  int d,p;
  for(int i=1;i<N;i++){
    for(int j=i+1;j<=N;j++){
      d=0;
      for(int k=1;k<=D;k++){
        d+=(X[i][k]-X[j][k])*(X[i][k]-X[j][k]);
      }
      p=0;
      while(p*p<d) p++;
      if(p*p==d) S++;
    }
  }
  printf("%d\n",S);
  return 0;
}

Measured memory_bytes: 1736
#include <bits/stdc++.h>
using namespace std;
template<typename tp>inline void r(tp &n){
	n=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while( isdigit(c)) n=n*10+c-48,c=getchar();	
}
inline long long dis(long long x,long long y){
	return (x*x+y*y);	
}
int main(){
	
	int n,d,ans=0;
	r(n),r(d);
	for(int i=1,x,y;i<=n;++i)
		r(x),r(y),ans+=(dis(x,y)<=1ll*d*d);
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 3752
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
#include<cmath>
#include<stack>
#include <algorithm>
#include <functional>
//#include<stdlib.h>
using namespace std;
int main() {
	int n, c = 0; bool w = false;
	cin >> n;
	vector<pair<int, int>>t(n);
	for (int a = 0; a < n; a++) { cin >> t[a].second >> t[a].first; }
	std::sort(t.begin(), t.end());
	for (int a = 0; a < n; a++)
	{
		c += t[a].second;
		if (c > t[a].first) { w = true; break; }
	}
	if (w) { cout << "No"; }
	else { cout << "Yes"; }

	return 0;
}

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

ans = 0
e = 0
for i, v in enumerate(b):
  if a[i] >= e:
      ans += e
      a[i] -= e
  else:
      ans += a[i]
      a[i] = 0
  e = 0
  if a[i] >= v:
      ans += v
  else:
      ans += a[i]
      e = v - a[i]
ans += min(a[-1], e)
print(ans)

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

int main()
{
    int w, a, b, aw, bw;
    cin >> w >> a >> b;
    aw=a+w, bw=b+w;
    if((b>=a and b<=aw) or (bw>=a and bw<=aw))cout <<0;
    else if(bw<a)cout << a-bw;
    else if(b>aw) cout << b-aw;
}


Measured memory_bytes: 3604
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
void swap(int & a,int & b){
int temp=a;
a=b;
b=temp;
}
ll k;
int n;
double d[100001];
ll b[100001];
ll f[100001];
ll c[100001];
 void solve(void){
 int i;
 while(k>0){

    if(k&1){

      for(i=1;i<n;i++)
            f[i]=b[c[i]];
            for(i=1;i<n;i++)
            b[i]=f[i];


    }

    k=k>>1;
     for(i=1;i<n;i++)
            f[i]=c[c[i]];
            for(i=1;i<n;i++)
            c[i]=f[i];








 }




 }
int main(){
int i,j;

cin>>n;
int  x[n+1];
for(i=1;i<=n;i++){
    cin>>x[i];


}

for(i=1;i<=n-1;i++){

    b[i]=i;
    c[i]=i;
    d[i]=x[i+1]-x[i];

}
ll m;
cin>>m>>k;
for(i=1;i<=m;i++){

    int y;
    cin>>y;
    swap(c[y-1],c[y]);

}
solve();
double po;
for(i=1;i<=n;i++){

    if(i==1||i==n)
        {po=x[i];
            printf("%.1f",(double)x[i]);}
    else
        {po=po+d[b[i-1]];
            printf("%.1f",po);}

    cout<<endl;
}




return 0;}


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

int main() {
  int n;

  cin >> n;

  int table[n];

  for(int i=0; i < n; i++) {
    cin >> table[i];
  }
  int west = table[0];
  int ans = 0;
  int maxN = 0;

  for(int i=0; i<n; i++) {
    maxN = max(maxN,table[i]);
    
    if(table[i] >= maxN) {
      ans++;
    }
  }
  cout << ans << endl;
}

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

using namespace std;

int rdmap[51][51];

void solve() {
    int n,m;
    cin >> n >> m;
    for(int i=0; i < m; ++i){
        int ai, bi;
        cin >> ai >> bi;
        ++rdmap[ai][bi];
        ++rdmap[bi][ai];
    }
    for (int i = 1; i <= n; ++i) {
        int cnt = 0;
        for (int j = 1; j <= n; ++j) {
            cnt += rdmap[i][j];
        }
        cout << cnt << endl;
    }

}

int main() {

    solve();
    return 0;
}


Measured memory_bytes: 3180
n=int(input())
xy=[list(map(int,input().split()))for _ in range(n)]
def gaisin(a,b,c,d,e,f):
  if (a-c)*(d-f)==(c-e)*(b-d):return ["ng"]
  aa=a**2
  bb=b**2
  cc=c**2
  dd=d**2
  ee=e**2
  ff=f**2
  py=((e-a)*(aa+bb-cc-dd)-(c-a)*(aa+bb-ee-ff))/(2*((e-a)*(b-d)-(c-a)*(b-f)))
  if a==c:px=(2*(b-f)*py-aa-bb+ee+ff)/(2*(e-a))
  else:px=(2*(b-d)*py-aa-bb+cc+dd)/(2*(c-a))
  return ["ok",px,py]
pxy=[]
for i in range(n-2):
  for j in range(i+1,n-1):
    for k in range(j+1,n):
      x1,y1=xy[i]
      x2,y2=xy[j]
      x3,y3=xy[k]
      gai=gaisin(x1,y1,x2,y2,x3,y3)
      if len(gai)==1:continue
      _,px,py=gai
      pxy.append([px,py])
for i in range(n-1):
  for j in range(i+1,n):
    x1,y1=xy[i]
    x2,y2=xy[j]
    px=(x1+x2)/2
    py=(y1+y2)/2
    pxy.append([px,py])
ans=10**10
for px,py in pxy:
  ans=min(ans,max(((px-x)**2+(py-y)**2)**(0.5)for x,y in xy))
print(ans)

Measured memory_bytes: 6260
N = int(input())
L = len(str(N))

ans = 0

for l in range(1, L, 2):
    if l != L:
        ans += 9 * 10 ** (l-1)

if L % 2 == 1:
    ans += N - (10 ** (L-1) - 1)

print(ans)


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

int main() {
	int n;cin>>n;
	vector<int> d(n);
	for(int i=0;i<n;i++){
		cin>>d[i];
	}
	sort(d.begin(),d.end());
	int ld=d[n/2-1];
	int rd=d[n/2];
	cout<<rd-ld<<endl;

	return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>

using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

const int iinf = 1 << 29;
const long long linf = 1ll << 61;

#define dump(x) cerr << #x << " : " << x << '\n'
#define MOD(x, y) (((y) + (x) % (y)) % (y))

int main(int argc, char* argv[])
{
	int N, A, B;
	scanf("%d%d%d", &N, &A, &B);
	if ((B - A) % 2 == 0) {
		printf("Alice\n");
	} else {
		printf("Borys\n");
	}

	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main() {
	int n, k1, k2, k4;

	scanf("%d", &n);
	k1 = k2 = k4 = 0;
	while (n--) {
		int a;

		scanf("%d", &a);
		if (a % 4 == 0)
			k4++;
		else if (a % 2 == 0)
			k2++;
		else
			k1++;
	}
	if (k2 > 0)
		k1++;
	printf(k1 <= k4 + 1 ? "Yes\n" : "No\n");
	return 0;
}


Measured memory_bytes: 128
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, K = map(int, readline().split())
A = np.array(read().split(), np.int32)

g = np.gcd.reduce(A)
cond = (K % g == 0) and (K <= A.max())
print('POSSIBLE' if cond else 'IMPOSSIBLE')

Measured memory_bytes: 33088
def main():
    from fractions import gcd

    MOD = 10 ** 9 + 7

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

    tmp = 1
    for a in A:
        tmp *= a // gcd(tmp, a)

    ans = 0
    for a in A:
        ans += (tmp // a)
    ans %= MOD

    print (ans)

if __name__ == '__main__':
    main()

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

using i64 = int64_t;

int garden[12][12]={0};

void init(){
    for(int i=0;i<=10;++i){
        for(int j=0;j<=10;++j)
            garden[i][j] = 0;
    }
}

int main(){
    int d, w;
    while(cin >> d >> w, d != 0){
        init();
        for(int i=0;i<d;++i){
            for(int j=0;j<w;++j){
                cin >> garden[i][j];
            }
        }

        int ans = 0;
        for(int top=0;top<d;++top){
            for(int left=0;left<w;++left){
                for(int bottom=top+2;bottom<d;++bottom){
                    for(int right=left+2;right<w;++right){
                        int mini = 11;
                        for(int i=left;i<=right;++i){
                            mini = min(mini, garden[top][i]);
                            mini = min(mini, garden[bottom][i]);
                        }
                        for(int i=top;i<=bottom;++i){
                            mini = min(mini, garden[i][left]);
                            mini = min(mini, garden[i][right]);
                        }
                        bool ok = true;
                        int sum = 0;
                        for(int i=top+1;i<bottom;++i){
                            for(int j=left+1;j<right;++j){
                                if(garden[i][j] >= mini){
                                    ok = false;
                                    break;
                                }
                                sum += mini - garden[i][j];
                            }
                            if(!ok)break;
                        }
                        if(ok)ans = max(ans, sum);
                    }
                }
            }
        }
        cout << ans << endl;
    }

    return 0;
}



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

int main(void) {
    ll K; cin >> K;
    ll ans=1;
    if(K%2==0) {
        cout << -1 << endl;
        return 0;
    }
    else {
        int x = 7 % K;
        for(int i=0; i<K; i++) {
            if(x == 0) {
                cout << ans << endl;
                return 0;
            }
            else {
                x = x*10 + 7;
                x= x%K;
                ans++;
            }
        }
    }
    cout << -1 << endl;
}

Measured memory_bytes: 3628
H, W, K =  [int(i) for i in input().split()]

masme = []
for i in range(H):
    masme.append(list(input()))

#print(masme)

h_p = []
for h in range(pow(2,H)):
    h_p.append( [int(i) for i in list(str(bin(h))[2:].zfill(H))] )

#print(h_p)

w_p = []
for w in range(pow(2,W)):
    w_p.append( [int(i) for i in list(str(bin(w))[2:].zfill(W))] )

#print(w_p)

def count(mas, h_b, w_b):
    ans = 0
    for i in range(H):
        for j in range(W):
            if h_b[i] * w_b[j] == 1 and mas[i][j] == "#" :
                ans += 1
    return ans


ans_cnt = 0

for h in h_p:
    for w in w_p:
        cnt = 0
        for i in range(H):
            for j in range(W):
                if h[i] * w[j] == 1 and masme[i][j] == "#" :
                    cnt += 1
        if(cnt == K):
            ans_cnt += 1

print(ans_cnt)

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

int main(){
  int n, a, b;
  cin >> n >> a >> b;
  long long ans = 0;
  vector<int> xi(n);
  for(int i=0; i<n; ++i) cin >> xi[i];
  for(int i=1; i<n; ++i){
    long long dis = xi[i]-xi[i-1];
    if(dis*a < b) ans += dis*a;
    else ans += b;
  }
  cout << ans << endl;
}

Measured memory_bytes: 640
#include <stdio.h>
#include <algorithm>
using namespace std;
using ll = long long;

int a, b;
int main() {
	scanf("%d %d", &a, &b);
	if (a > b)
		swap(a, b);
	for (int i = 0; i < b; i++)
		printf("%d", a);
	printf("\n");
}

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


int main(){
	int N;
	int array[100010];
	bool check[100010];
	int kind=0;
	cin >> N;
	for(int i=0;i<100010;i++){
		check[i] = true;
	}
	for(int i=0;i<N;i++){
		cin >> array[i];
		if(check[array[i]]){
			kind++;
			check[array[i]]=false;
		}
	}
	if(kind%2==1){
		cout << kind << endl;
	}else{
		cout << kind - 1 << endl;
	}
	
	return 0;
}


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

using namespace std;
typedef long long ll;

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

  bool from1[200000] = {}, to2[200000] = {};

  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    if (a == 1) {
      from1[b] = true;
    }
    if (b == N) {
      to2[a] = true;
    }
  }

  for (int i = 0; i < N; i++){
    if (from1[i] && to2[i]) {
      cout << "POSSIBLE" << endl;
      return 0;
    }
  }
  cout << "IMPOSSIBLE" << endl;
  return 0;
}

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

using namespace std;

bool solve(const string& s){
    if(s.size()%2) return false;
    for(int i=0;i<s.size();i++){
        if(s[i] != "hi"[i%2]) return false;
    }
    return true;
}

int main(){
    string S;
    while(cin >> S){
        cout << (solve(S) ? "Yes" : "No") << endl;
    }
}

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

#define FOR(s, i, n) for(int i = s; i n; i++)
typedef long long ll;
const int INF = 1e9;
vector<vector<int>> adj;
vector<int> ans;
vector<int> lis;
vector<int> val;
void dfs(int u, int par){
	ans[u] = lis.size();
	for (auto it: adj[u]){
		if(it != par){
			if (val[it] > lis.back()){
				lis.push_back(val[it]);
				dfs(it, u);
				lis.pop_back();
			}else{
				int pos = lower_bound(lis.begin(), lis.end(), val[it]) - lis.begin();
				if (pos != -1){
					int last = lis[pos];
					lis[pos] = val[it];
					dfs(it, u);
					lis[pos] = last;
				}
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	cin>>n;
	adj.resize(n, vector<int>());
	ans.resize(n, 0);
	val.resize(n);
	for (int i = 0; i < n; i++){
		cin>>val[i];
	}
	int u, v;
	for (int i = 0; i < n-1; i++){
		cin>>u>>v;
		u--; v--;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	lis.push_back(val[0]);
	dfs(0, -1);
	for (auto it: ans){
		cout<<it<<'\n';
	}
	return 0;
}

Measured memory_bytes: 30128
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next()); 
        int[][] a = new int[12][10];
        for (int k = 0; k < n; k++) {
            int b = Integer.parseInt(sc.next());
            int f = Integer.parseInt(sc.next());
            int r = Integer.parseInt(sc.next());
            int v = Integer.parseInt(sc.next());
            switch (b) {
                case 1 :
                    a[f-1][r-1] += v;
                    break;
                case 2 :
                    a[3+f-1][r-1] += v;
                    break;
                case 3 :
                    a[6+f-1][r-1] += v;
                    break;
                case 4 :
                    a[9+f-1][r-1] += v;
                    break;
                default :
                    break;
            }
        } 
        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 10; j++)
                System.out.print(" " + a[i][j]);
            System.out.println();
            if ((i == 2) || (i == 5) || (i == 8))
                System.out.println("####################");
        }
    }
}


Measured memory_bytes: 28476
#include<bits/stdc++.h>
#include<vector>
#include<math.h>
#include<string.h>
using namespace std;
#define MAX 3005
#define MOD 998244353
#define NIN -100000000
#define EPS 0.0000000001
int dp[MAX][MAX];
int A[MAX];
int sets(int index,int sum)
{
    if(index<0)
    {
        return (sum==0);
    }
    if(dp[index][sum]!=-1)
    {
        return dp[index][sum];
    }
    dp[index][sum]=(sets(index-1,sum)*2)%MOD;
    if(A[index]<=sum)
    {
        dp[index][sum]=(dp[index][sum]+sets(index-1,sum-A[index]))%MOD;
    }
    return dp[index][sum];
}
int main()
{
    int N,S,i,j;
    scanf("%d %d",&N,&S);
    for(i=0;i<N;i++)
    {
        scanf("%d",&A[i]);
        for(j=0;j<=S;j++)
        {
            dp[i][j]=-1;
        }
    }
    int ans=sets(N-1,S);
    printf("%d",ans);
    return 0;
}


Measured memory_bytes: 39156
#include <bits/stdc++.h>
using namespace std;
using vi=vector<int>;
using vvi=vector<vi>;
using vs=vector<string>;
using msi=map<string,int>;
using mii=map<int,int>;
using pii=pair<int,int>;
using vlai=valarray<int>;
using ll=long long;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1e9
#define EPS 1e-9

int main(){
	int n;
	while(cin>>n,n){
	    vs s(n);
	    vi depth(n);
	    rep(i,n){
	        cin>>s[i];
	        depth[i]=upper_bound(all(s[i]),'.')-s[i].begin()-1;
	    }
	    range(i,1,n){
	        s[i][depth[i]]='+';
	        int samepos=-1;
	        range(j,i+1,n){
	            samepos=j;
	            if(depth[j]<=depth[i])break;
	        }
            if(depth[i]==depth[samepos])
                range(j,i+1,samepos) s[j][depth[i]]='|';
	    }
	    for(auto c:s){
	        replace(all(c),'.',' ');
	        cout<<c<<endl;
	    }
	}
	return 0;
}

Measured memory_bytes: 3652
#pragma GCC optimize("O3")

#define _GLIBCXX_DEBUG
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
using namespace std;

/*----------macros----------*/

//output================
#define endl '\n'
#define fcout cout << fixed << setprecision(15)

//typedef===============
typedef long long       ll;
typedef long double     ld;
typedef pair<int, int>  Pii;
typedef pair<ll, ll>    Pll;

//const number==========
constexpr ll INF9   = (ll)1e9 + 1;
constexpr ll INF18  = (ll)1e18 + 1;
constexpr ll MOD    = 1000000007;
constexpr ld PI     = 3.141592653589793L;

//member================
#define pb push_back
#define eb emplace_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second

//others================
#define all(x)          (x).begin(), (x).end()
#define rall(x)         (x).rbegin(), (x).rend()
#define rep(i, n)       for(int i = 0; (i) < (n); ++(i))
#define rrep(i, n)      for(int i = n - 1; (i) >= 0 ; --(i))
#define For(i, a, b)    for(int i = (a); (i) < (b) ; ++(i))
#define CtoI(c)         int((c)) - int('0')

//functions=============
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

//vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
//vector<int> dx2 = { 1,1,0,-1,-1,-1,0,1 }, dy2 = { 0,1,1,1,0,-1,-1,-1 };

/*--------additional--------*/



/*----------main------------*/

int main() {
/*----------fastio----------*/
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
/*----------solve-----------*/

    int n, k; cin >> n >> k;
    ll ans = k;
    for(int i = 1; i < n; ++i){
        ans *= k-1;
    }

    cout << ans << endl;

return 0;
}

Measured memory_bytes: 3648
#!/usr/bin/env python3

import sys
import numpy as np
from collections import Counter

def II(): return int(input())
def MII(): return map(int, input().split())
def LII(): return list(map(int, input().split()))


def main():
    N = int(input())
    A = LII()
    A.sort() 
    
    if N == 1:
        print(1)
        return

    ax = max(A) + 1
    dp = [0] * ax
    for ai in A:
        da = dp[ai]
        if da > 1:
            continue
        dp[ai] += 1
        if da == 0:
            for aj in range(2*ai, ax, ai):
                dp[aj] = 2

    print(sum(filter(lambda x: x == 1, dp)))


if __name__ == '__main__':
    main()


Measured memory_bytes: 51480
using System;
using System.Collections.Generic;
using static AtCoderer.Exter;
using static System.Math;
using System.Linq;

namespace AtCoderer
{

    public class App
    {
        public static void Solve()
        {
            var va = readarr[1];
          	int sum =0,c=1;
          	foreach(var l in readarr)
            {
              	sum+=l;
              	if(sum <= va)
                  	c++;
            }
          	Console.WriteLine(c);
        }
        public static void Main(string[] args)
        {
            Solve();
            Console.ReadKey();
        }
    }
    public static class Exter
    {
        public static int Max(params int[] p) => p.Max();
        public static long Max(params long[] p) => p.Max();
        public static int Min(params int[] p) => p.Min();
        public static long Min(params long[] p) => p.Min();
        public static int Gcd(int a, int b) => a > b ? GcdRecursive(a, b) : GcdRecursive(b, a);
        private static int GcdRecursive(int a, int b) => b == 0 ? a : GcdRecursive(b, a % b);
        public static void EnumArr<t>(this IEnumerable<t> v)
        {
            Console.WriteLine(string.Join(",", v));
        }
        public static string ToString(this IEnumerable<char> v)
        {
            return string.Join(",", v);
        }
        public static int[] readarr
        {
            get
            {
                return Console.ReadLine().Split().Select(s => int.Parse(s)).ToArray();
            }
        }
        public class UnionFind
        {
            private int[] Parent;
            private int GetRoot(int v)
            {
                if (Parent[v] < 0)
                    return v;
                else
                    return Parent[v] = GetRoot(Parent[v]);
            }
            public UnionFind(int size)
            {
                Parent = new int[size];
                for (int i = 0; i < size; i++)
                    Parent[i] = -1;
            }
            public bool AreGrouped(int a, int b)
            {
                return GetRoot(a) == GetRoot(b);
            }
            public void Connect(int a, int b)
            {
                a = GetRoot(a);
                b = GetRoot(b);
                if (a == b) return;
                if (Parent[b] < Parent[a])
                {
                    Parent[b] += Parent[a];
                    Parent[a] = b;
                }
                else
                {
                    Parent[a] += Parent[b];
                    Parent[b] = a;
                }
            }
            public int GetGroupSize(int a)
            {
                return -Parent[GetRoot(a)];
            }
        }
    }
}


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

using namespace std;
typedef long long int ll;

int main()
{
    int n;
    cin >> n;
    vector<int>l(n),r(n);
    for(int i = 0; i < n; i++) cin >> l[i] >> r[i];
    sort(l.begin(),l.end()),sort(r.begin(),r.end());
    int ans = 0;
    if(n % 2 == 1)
    {
        int l1 = l[n/2];
        int r1 = r[n/2];
        ans = r1 - l1 + 1;
    }
    else
    {
        int l2 = l[n/2-1]+l[n/2];
        int r2 = r[n/2-1]+r[n/2];
        ans =  r2 - l2 + 1;
    }
    cout << ans << endl;
}

Measured memory_bytes: 4820