akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<vector>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<map>


using namespace std;

int main(void){
 int A,B,C,K;
 int sum=0;
 cin>>A>>B>>C>>K;
 
 if(K<=A){
  sum=K;
  cout<<sum<<endl;
  return 0;
 }
 else {
  sum=A;
  K-=A;
 }

 if(K<=B){
  cout<<sum<<endl;
  return 0;
 }
 else K-=B;

 cout<<sum-K<<endl; 

 return 0;
}


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

// data structure
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <vector>

#include <algorithm>
#include <cmath>

using namespace std;

int main(int argc, char const *argv[]) {
  long long int a, b, c, k;
  long long int max = 0;

  cin >> a >> b >> c >> k;

  if (k >= a) {
    max += a;
    k -= a;
  } else {
    max += k;
    k = 0;
  }

  k -= b;

  if (k > 0)
    max -= k;

  cout << max << endl;
  return 0;
}


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

int main() {
    int num;
    cin >> num;
  	int count = 0;
    for(int i = 0; i < 3; ++i)
    {
      if(num % 10 == 1) count++;
      num = num / 10;
    }
  
  	cout << count << endl;
}

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

using namespace std;

int n;
string s;

bool ok(int a[3]) {
	int cnt = 0;
	for (int i = 0; i < n; ++i) {
		if (a[cnt] == s[i] - '0') cnt++;
		if (cnt == 3) return true;
	}
	return false;
}

int main() {
	cin >> n;
	cin >> s;
	int ans = 0;
	int a[3];
	for (a[0] = 0; a[0] < 10; ++a[0])
		for (a[1] = 0; a[1] < 10; ++a[1])
			for (a[2] = 0; a[2] < 10; ++a[2])
				if (ok(a)) ans++;
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };

#define rep(i, N) for (int i = 0; i < N; i++)
#define pb push_back

ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

int main() {
	int N, M; cin >> N >> M;
	vector<int> a(N);
	rep(i, N) scanf("%d", &a[i]);
	vector<int> b(100001);
	rep(i, N) b[a[i]]++;
	vector<int> c(M), d(M);
	rep(x, 100001) {
		c[x % M] += b[x];
		d[x % M] += b[x] / 2;
	}
	int ans = 0;
	for (int x = 0; x * 2 <= M; x++) {
		if (x == 0 || x * 2 == M) {
			ans += c[x] / 2;
			continue;
		}
		int y = M - x;
		if (c[x] > c[y]) {
			swap(c[x], c[y]);
			swap(d[x], d[y]);
		}
		ans += c[x] + min(d[y], (c[y] - c[x]) / 2);
	}
	cout << ans << endl;
}


Measured memory_bytes: 1792
#include<stdio.h>
int R=1,C=1,H[2000010],N[2000010];
int hyouka(int a,int b){
  if(C<b)return 1;
  if(C<a||b==0)return 0;
  return N[H[a]]>N[H[b]]?1:0;
}
void hin(int a){
  int i=C++;
  for(N[H[0]=R]=a;hyouka(0,i/2);i/=2)H[i]=H[i/2];
  H[i]=R++;
}
int hout(){
  int rt=H[1],i,j,k=H[--C];
  for(i=1;hyouka(i,C);i=j)H[i]=H[j=i*2+1-hyouka(i*2,i*2+1)];
  H[i/2]=k;
  return rt;
}
int main(){
  int a;
  char s[100];
  while(scanf("%s",s),s[2]-'d'){
    if(s[2]=='s'){
      scanf("%d",&a);
      hin(a);
    }
    else printf("%d\n",N[hout()]);
  }
  return 0;
}

Measured memory_bytes: 14932
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
using namespace std;

char str[123456];
int n;
char ch(int x)
{
	return str[(x % n + n) % n];
}

int main(void)
{
	cin >> n;
	cin >> str;
	for (int b = 0; b < 4; ++b)
	{
		int bit = b;
		bool cl = b & 2, cm = b & 1;
		bool lef = b & 2, mid = b & 1;
		string ans;
		for (int i = 0; i < n; ++i)
		{
			ans.push_back(mid ? 'S' : 'W');
			bool cir = ch(i) == 'o';
			bool right = lef ^ mid ^ cir;
			lef = mid;
			mid = right;
		}
		if (cl == lef && cm == mid)
		{
			cout << ans << endl;
			return 0;
		}
	}
	cout << -1 << endl;
	return 0;
}


Measured memory_bytes: 696
//default
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
typedef pair<int, int> P_i;
typedef pair<double,double> P_d;
#define rep(i,n) for(int i=0;i<(n);++i)
#define alrep(i,j,n) for(int i=0;i<(n);++i)for(int j=i+1;j<(n);++j)
#define Yes cout << "Yes" << endl;
#define No cout << "No" << endl;int ans=0;
#define answer cout << ans << endl;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const int MOD=1e9+7;
const long long INF = 1LL << 60;

signed main(){
  int N,ans=0;
  cin >> N;
  int A[N],B[N],C[N];
  rep(i,N){
    cin >> A[i];
  }
  sort(A,A+N);
  rep(i,N){
    cin >> B[i];
  }
  rep(i,N){
    cin >> C[i];
  }
  sort(C,C+N);
  rep(i,N){
    int a_num=lower_bound(A,A+N,B[i])-A;
    int c_num=N-(upper_bound(C,C+N,B[i])-C);
    ans+=a_num*c_num;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 2560
#include <stdio.h>
int main(){
	long int n;
	long int a[5];
	scanf("%ld%ld%ld%ld%ld%ld",&n,&a[0],&a[1],&a[2],&a[3],&a[4]);
	
	long int min=a[0];
	for(int i=1;i<5;i++){
		if(min>=a[i]){
			min=a[i];
		}
	}
	
	long int time = 0;
	time = (n%min==0?n/min:n/min+1) + 4;
	printf("%ld",time);
	return 0;
}

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

int main() {
    int r;
    cin >> r;
  	string ans = "No";
    for(int i=0; i<10; i++){
      for(int j=0; j<10; j++){
        if(i * j == r){
          ans = "Yes";
        }
      }
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <numeric>
#include <cmath>
#include <limits>
#include <stdio.h>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
ll Max(ll(a), ll(b), ll(c)) {
	return max(max(a, b), c);
}
ll Min(ll(a), ll(b), ll(c)) {
	return min(min(a, b), c);
}





int main() {
	ll k = 1e9;
	ll S;
	cin >> S;
	if (S == 1e18) {
		cout<<"0 0 1000000000 0 0 1000000000"<<endl;
		return 0;
	}
	cout << 0<<" "<<0<<" "<<k<<" "<<1<<" "<<k-(S%k)<<" "<<(S+(k - (S % k)))/k<< endl;
}


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

template<class T> inline bool chmax(T& a, T b) {
  if ( a < b ) {
    a = b;
    return true;
  }
  return false;
}
long long dp[110][100100];

int main()
{
  int N {0};
  long long W {0};
  std::cin >> N >> W;
  long long weight_value_table[N][2];
  for ( int i = 0; i < N; i++ ) {
    for ( int j = 0; j < 2; j++ ) {
      std::cin >> weight_value_table[i][j];
    }
  }

  for ( int i = 0; i < N; i++ ) {
    for ( int sum_w = 0; sum_w <= W; sum_w++ ) {
      if ( sum_w - weight_value_table[i][0] >= 0 ) {
        chmax(dp[i+1][sum_w], dp[i][sum_w - weight_value_table[i][0]] + weight_value_table[i][1]);
      } 
      chmax(dp[i+1][sum_w], dp[i][sum_w]);
    }
  }
  std::cout << dp[N][W] << std::endl;
  return 0;
}


Measured memory_bytes: 79360
# 初期入力
N,K = (int(x) for x in input().split(" "))
H = list(map(int, input().split()))
tuujou_attack = 1

# N種類のモンスター、K回の必殺技、モンスターは　H　の体力
# 体力の多いモンスターから必殺技で倒す。必殺技が使えなくなったら通常攻撃
nokori_kaisu = 0
H_sorted = sorted(H)
if N <= K:
    nokori_kaisu = 0
else:
    nokori_hissatuwaza = N -K
    del H_sorted[nokori_hissatuwaza:]
    nokori_kaisu = sum( H_sorted ) # 体力少ないほうから　N-K　まで、通常攻撃「１」

print(nokori_kaisu)

Measured memory_bytes: 26024
import scala.math._
import scala.collection.mutable.ListBuffer

object Main {
  //rt.gc()??§??¬??????????????¬?????????????????????
  //val rt = Runtime.getRuntime()
  val sc = new java.util.Scanner(System.in)
  def main(args: Array[String]) {
    println((1 to 10).map(_ => sc.nextInt).sum)
  }
}

Measured memory_bytes: 45204
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cerr << "[(" << __LINE__ << ") " << (#x) << "]: " << x << endl;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    int s, w;
    cin >> s >> w;

    cout << (w < s ? "safe" : "unsafe") << "\n";
}


Measured memory_bytes: 3652
#include <stdio.h>
#include <stdio.h>

int main(void)
{
    int a, b, c, t, first;
    int i, j;

    scanf("%d %d %d", &a, &b, &c);

    i = 1;
    first = a % b;
    do {
        i++;
        t = a * i % b;
        if (t == c) {
            printf("YES\n");
            return 0;
        }
    } while (t != first);
    printf("NO\n");

    return 0;
}

Measured memory_bytes: 128
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include<math.h>
using namespace std;
using ll = long long;
const ll INF = 100100100100100;
const ll mod = 1000000007;

int main()
{
	ll N;
	cin >> N;
	vector<ll> A(N);
	for (int i = 0; i < N; i++) cin >> A[i];
	ll odd = 0;
	for (int i = 0; i < N; i++) {
		if (A[i] % 2 == 1) odd++;
	}
	if (odd % 2 == 1) cout << "NO" << endl;
	else cout << "YES" << endl;
}


Measured memory_bytes: 1024
//Shunji Lin 08-144505
#include <iostream>
#include <string>

using namespace std;

int reachable = 0;

void DFS(int grid[20][20], int visited[20][20],  int row_pos, int col_pos, int H, int W);

void DFS_aux(int grid[20][20], int visited[20][20], int row_pos, int col_pos, int H, int W) {
  if (grid[row_pos][col_pos] && !visited[row_pos][col_pos]) {
    DFS(grid, visited, row_pos, col_pos, H, W);
  }
    
}
	 
void DFS(int grid[20][20], int visited[20][20], int row_pos, int col_pos, int H, int W) {
  visited[row_pos][col_pos] = true;
  reachable += 1;
  if (!(row_pos == 0)) {
    DFS_aux(grid, visited, row_pos-1, col_pos, H, W); //up
  }
  if (!(col_pos == 0)) {
    DFS_aux(grid, visited, row_pos, col_pos-1, H, W); //left
  }
  if (!(row_pos == H-1)) {
    DFS_aux(grid, visited, row_pos + 1, col_pos, H, W); //down
  }
  if (!(col_pos == W-1)) {
    DFS_aux(grid, visited, row_pos, col_pos + 1, H , W); //right
  }
}
      
    


int main() {
  while (true) {
    int grid[20][20] = {{false}};
    int visited[20][20] = {{false}};
    reachable = 0;
    int man_row = -1, man_col = -1;
    int W, H;
    cin >> W >> H;
    if (W == 0 && H == 0) break;
    for (int i = 0; i < H; i++) {
      string line;
      cin >> line;
      for (int j = 0; j < W; j++) {
	if (line[j] == '@') {
	  grid[i][j] = true;
	  man_row = i;
	  man_col = j;
	} else if (line[j] == '.') {
	  grid[i][j] = true;
	}
      }
    }
    /*
    //print out grid
    for (int i = 0; i < H; i++) {
      for (int j = 0; j < W; j++) {
	if (grid[i][j] == true) {
	  cout << 'b';
	} else if (grid[i][j] == false) {
	  cout << 'r';
	} 
      }
      cout << endl;
    }
    */
    
    DFS(grid, visited,  man_row, man_col, H, W );
    cout << reachable << endl;
  }
}

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

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

    println!("{}", answer);
}

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let n: usize = iterator.next().unwrap().parse().unwrap();
    let mut cards1: Vec<Card> = Vec::with_capacity(n);
    let mut cards2: Vec<Card> = Vec::with_capacity(n);
    for _i in 0..n {
        let input = iterator.next().unwrap().to_string();
        cards1.push(Card::new(&input));
        cards2.push(Card::new(&input));
    }

    let mut result = String::new();

    // Bubble Sort
    for i in 0..n {
        for j in ((i + 1)..n).rev() {
            if cards1[j].number < cards1[j - 1].number {
                cards1.swap(j, j - 1);
            }
        }
    }
    result += &cards1.iter().map(|it| it.to_string()).collect::<Vec<String>>().join(" ");
    result += "\nStable\n"; // always stable

    // Selection Sort
    for i in 0..n {
        let mut minj = i;
        for j in i..n {
            if cards2[j].number < cards2[minj].number {
                minj = j;
            }
        }
        cards2.swap(i, minj);
    }
    result += &cards2.iter().map(|it| it.to_string()).collect::<Vec<String>>().join(" ");
    result += if is_stable(&cards1, &cards2) { "\nStable" } else { "\nNot stable" };

    return result.trim().to_string();
}

fn is_stable(cards1: &Vec<Card>, cards2: &Vec<Card>) -> bool {
    for i in 0..cards1.len() {
        let c1 = &cards1[i];
        let c2 = &cards2[i];
        if c1.suit != c2.suit || c1.number != c2.number {
            return false;
        }
    }
    true
}

struct Card {
    suit: char,
    number: usize,
}

impl Card {
    fn new(input: &String) -> Card {
        let mut chars = input.chars();
        let s: char = chars.next().unwrap();
        let n: usize = chars.next().unwrap().to_string().parse().unwrap();
        Card { suit: s, number: n }
    }

    fn to_string(&self) -> String {
        format!("{}{}", self.suit, self.number)
    }
}



Measured memory_bytes: 5040
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define int long long
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define yn(x) ((x) ? "Yes" : "No")

typedef pair <int, int> ii;
typedef pair <int, ii> iii;

template <class T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T> using ordered_multiset = tree <T, null_type, less_equal <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int siz = 2e5 + 10;
const int SIZ = 1e6 + 10;
const int mod = 1e9 + 7;
const int maxx = 2e9;
const int MAXX = 1e18;
const string file = "1";



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

//    freopen ((file + ".inp").c_str(), "r", stdin);
//    freopen ((file + ".out").c_str(), "w", stdout);

    int n;
    cin >> n;
    int ans = 0, mx = 0;
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        ans += max(mx - a, 0LL);
        mx = max(mx, a);
    }

    cout << ans << "\n";

//    cerr << "Time: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";

    return 0;
}


Measured memory_bytes: 3648
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#include<cmath>
using namespace std;

int main(){
    int n, m;
    while(cin >> n >> m, n){
        int a[n], w[m];
        for(int i = 0; i < n; i++)  cin >> a[i];
        for(int i = 0; i < m; i++)  cin >> w[i];
        set<int> s;
        for(int i = 0; i < pow(3,m); i++){
            int x = 0, cp = i;
            for(int j = 0; j < m; j++)  x += (cp%3-1)*w[j], cp /= 3;
            s.insert(x);
        }
        vector<int> ng;
        for(int i = 0; i < n; i++)  if(s.count(a[i]) == 0)  ng.push_back(a[i]);
        if(ng.size() == 0){
            cout << 0 << endl;
            continue;
        }
        set<int> ok;
        for(int i : s){
            ok.insert(abs(i-ng[0]));
        }
        for(int i = 1; i < ng.size(); i++){
            set<int> nok;
            for(int x : ok) if(s.count(x+ng[i]) || s.count(abs(x-ng[i])))   nok.insert(x);
            ok = nok;
        }
        cout << (ok.empty() ? -1 : *ok.begin()) << endl;
    }
    return 0;
}


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

struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;

/* cpp template {{{ */

/* short */
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)
#define X real()
#define Y imag()

/* REPmacro */
#define REPS(i, a, n) for (ll i = (a); i < (ll)(n); ++i)
#define REP(i, n) REPS(i, 0, n)
#define RREP(i, n) REPS(i, 1, n + 1)
#define DEPS(i, a, n) for (ll i = (a); i >= (ll)(n); --i)
#define DEP(i, n) DEPS(i, n, 0)
#define EACH(i, n) for (auto&& i : n)

/* debug */
#define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n';

/* alias */
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;
using D = double;
using P = complex<D>;
using vs = vector<string>;
template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

/* const */
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7;
const D EPS = 1e-9;
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

/* func */
inline bool inside(int y, int x, int H, int W) {return y >= 0 && x >= 0 && y < H && x < W;}
inline int in() {int x; cin >> x; return x;}
inline ll IN() {ll x; cin >> x; return x;}
inline vs split(const string& t, char c) {vs v; stringstream s(t); string b; while(getline(s, b, c)) v.eb(b); return v;}
template <typename T> inline bool chmin(T& a, const T& b) {if (a > b) a = b; return a > b;}
template <typename T> inline bool chmax(T& a, const T& b) {if (a < b) a = b; return a < b;}
template <typename T, typename S> inline void print(const pair<T, S>& p) {cout << p.first << " " << p.second << endl;}
template <typename T> inline void print(const T& x) {cout << x << '\n';}
template <typename T, typename S> inline void print(const vector<pair<T, S>>& v) {for (auto&& p : v) print(p);}
template <typename T> inline void print(const vector<T>& v, string s = " ") {REP(i, v.size()) cout << v[i] << (i != (ll)v.size() - 1 ? s : "\n");}
// clang-format on
/* }}} */

signed main() 
{
  string s;
  cin >> s;
  int count=0;
  for(int i=0;i<3;i++)
  {
    if(s[i]=='1')
      count++;
  }
  cout << count << endl;
  return 0;
}

Measured memory_bytes: 256
n = gets.to_i
as = gets.chomp.split.map(&:to_i)
gcd_f = [as[0]]
gcd_b = [as[-1]]
max = 0
(1..n-1).each do |i|
  gcd_f.push(as[i].gcd(gcd_f[-1]))
  gcd_b.push(as[n-1-i].gcd(gcd_b[-1]))
end
(0..n-3).each do |i|
  max = [max,gcd_f[i].gcd(gcd_b[n-3-i])].max
end
max = [max,gcd_f[n-2],gcd_b[n-2]].max
puts max
STDERR.print "#{gcd_f} \n"
STDERR.print "#{gcd_b} \n" 

Measured memory_bytes: 18440
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
#include <complex>
#include <cstring>
using namespace std;

using ll = long long;
using P = pair<int, int>;
constexpr int INF = 1001001001;
constexpr int mod = 1000000007;
// constexpr int mod = 998244353;

template<class T>
inline bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}
template<class T>
inline bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

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

    int N, M;
    cin >> N >> M;
    vector<int> p(M), q(M), c(M);
    vector<vector<int>> table(N, vector<int>(1, 0));
    for(int i = 0; i < M; ++i){
        cin >> p[i] >> q[i] >> c[i];
        --p[i], --q[i];
        table[p[i]].emplace_back(c[i]);
        table[q[i]].emplace_back(c[i]);
    }
    map<P, int> mp;
    int cur_idx = 0;
    vector<P> vs;
    for(int i = 0; i < N; ++i){
        sort(table[i].begin(), table[i].end());
        table[i].erase(unique(table[i].begin(), table[i].end()), table[i].end());
        for(int& j : table[i]){
            mp[P(i, j)] = cur_idx++;
            vs.emplace_back(i, j);
        }
    }
    int K = mp.size();
    vector<vector<P>> graph(K);
    for(int i = 0; i < M; ++i){
        int u0 = mp[P(p[i], 0)], u1 = mp[P(p[i], c[i])];
        int v0 = mp[P(q[i], 0)], v1 = mp[P(q[i], c[i])];
        graph[u0].emplace_back(v1, 1);
        graph[u1].emplace_back(v1, 0);
        graph[u1].emplace_back(v0, 0);
        graph[v0].emplace_back(u1, 1);
        graph[v1].emplace_back(u1, 0);
        graph[v1].emplace_back(u0, 0);
    }
    vector<int> dist(K, INF);
    dist[0] = 0;
    deque<P> deq;
    deq.emplace_back(0, 0);
    while(!deq.empty()){
        int d = deq.front().first, from = deq.front().second;
        deq.pop_front();
        for(auto& e : graph[from]){
            int to = e.first, cost = e.second;
            if(!cost){
                if(chmin(dist[to], d))  deq.emplace_front(dist[to], to);
            }
            else{
                if(chmin(dist[to], d + 1))  deq.emplace_back(dist[to], to);
            }
        }
    }
    int goal = mp[P(N - 1, 0)];
    if(dist[goal] == INF)   cout << -1 << endl;
    else    cout << dist[goal] << endl;
}

Measured memory_bytes: 80064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define UM unordered_map
#define ALL(a) (a).begin(), (a).end()
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
typedef pair<ll, ll> pii;
const ll INF = 1LL << 58;
const ll MOD = 1000000007;
struct Edge
{
    ll s, t, d;
};
typedef vector<vector<Edge>> Graph;
typedef vector<pii> vpii;
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}

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

    int tmpdp[4] = {0};
    int dp[4] = {0};
    dp[3] = 1;
    REP(i, S.size())
    {
        REP(i, 3)
        tmpdp[i] = 0;

        if (S[i] == 'A')
            tmpdp[0] = dp[3];
        else if (S[i] == 'B')
            tmpdp[1] = dp[0];
        else if (S[i] == 'C')
            tmpdp[2] = dp[1];
        else
        {
            tmpdp[0] = dp[0] * 2 + dp[3];
            tmpdp[1] = dp[1] * 2 + dp[0];
            tmpdp[2] = dp[2] * 2 + dp[1];
            dp[3] *= 3;
        }
        REP(i, 4)
        {
            dp[i] += tmpdp[i];
            dp[i] %= MOD;
        }
        // REP(i, 4)
        // cout << dp[i] << " ";
        // cout << endl;
    }
    cout << dp[2] << endl;

    // system("pause");
}

Measured memory_bytes: 512
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>
#include<vector>
#define rep(j, n) for (int i = j; i < n; i++)
#define repd(j, n) for (int i = j; i > n; i--)
#define ll long long
using namespace std;

long a[114514], n, k, i, j, x, c, ans;
int main()
{
	cin >> n >> k;
	for (i = 0; i < n; ++i)cin >> a[i];
	for (i = 62; i >= 0; --i) {
		c = 0;
		for (j = 0; j < n; ++j)c += (a[j] >> i) & 1;
		if (2 * c < n && (x | (1L << i)) <= k)x |= 1L << i;
	}
	ans= 0;
	for (i = 0; i < n; ++i)ans += x ^ a[i];
	cout << ans << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <climits>
#include <unistd.h>
#include <cmath>
using namespace std;
int main(){
    int inp;
    cin >> inp;
    for (int i = 0; i < 10000; ++i){
        int temp = inp + i;
        int res = temp%10;
        bool ok = true;
        while (temp){
            if (res != temp%10)
                ok = false;
            temp = temp/10;
        }
        if (ok){
            cout << inp + i; 
            break;
        }
    }
    return 0;
}


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

using namespace std;

const int INF = INT_MAX;

int main() {
    ios::sync_with_stdio(false);
    int n, ans = 0;
    string s;
    cin >> n >> s;
    for (auto i = 1; i < n; i++){
        ans += s[i] == s[i-1];
    }
    cout << n - ans;
}

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

int main() {
  int N, L;
  cin >> N >> L;
  vector<string> s(N);
  for (int i = 0; i < N; i++) cin >> s[i];
  sort(s.begin(), s.end());
  for (int i = 0; i < N; i++) cout << s[i];
  cout << endl;
}

Measured memory_bytes: 3704
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) debug(x) debug(y);
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))
const int MOD = 1e9 + 7;

template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }

int dp[100005][20];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	string s;
	cin >> s;
	int n = s.size();
	rep(i, 100005) rep(j, 20) dp[i][j] = 0;
	dp[0][0] = 1;
	repn(i, 1, n + 1){
		if(s[i - 1] == '?'){
			rep(k, 10) rep(j, 13){
				int cur = ((10 * j) + k) % 13;
				(dp[i][cur] += dp[i - 1][j]) %= MOD;
			}
		}
		else{
			rep(j, 13){
				int cur = ((10 * j) + (s[i - 1] - '0')) % 13;
				(dp[i][cur] += dp[i - 1][j]) %= MOD;
			}
		}
	}
	cout << dp[n][5] << endl;
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/


Measured memory_bytes: 8320
#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 ans = n;
	for (int i = 1; i < n; i++)
		if (d[i] == d[i - 1])
			ans--;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
//...Bismillahir Rahmanir Rahim...
// Code by    Asad Bin Saber

#include <bits/stdc++.h>

using namespace std;

// typedefs...
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<ll, ll> pll;

// constants...
const double PI = acos(-1);

// defines...
#define MP make_pair
#define PB push_back
#define fi first
#define se second
#define si(a) scanf("%d", &a)
#define sii(a, b) scanf("%d%d", &a, &b)
#define siii(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define sl(a) scanf("%lld", &a)
#define sll(a, b) scanf("%lld%lld", &a, &b)
#define slll(a, b, c) scanf("%lld%lld%lld", &a, &b, &c)

int gcd(int a, int b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}
ll lcm(ll a, ll b)
{
    return (a/gcd(a, b)*b);
}
ll comb(ll a, ll b)
{
    ll x = max(a-b, b), ans=1;

    for(ll K=a, L=1; K>=x+1; K--, L++){
        ans *= K;
        ans /= L;
    }

    return ans;
}


vector<int> primes;
vector<bool> mark(10002);
void sieve(int n)
{
    int i, j, limit = sqrt(n*1.) + 2;

    mark[1] = 1;

    for(i = 4; i<=n; i+=2) mark[i] = 1;

    primes.push_back(2);

    for(i = 3; i <= n; i += 2)
    {
        if(!mark[i])
        {
            primes.push_back(i);

            if(i<=limit)
            {
                for(j = i*i; j <= n; j += i*2)
                {
                    mark[j] = 1;
                }
            }
        }
    }
}
int divs(int n) {
	int cnt, tot=1, i;
	
	for(i=0; i<(int)primes.size() && (primes[i]*primes[i])<=n; i++) {
		if(n%primes[i]==0) {
			cnt=1;
			
			while(n%primes[i]==0) {
				n/=primes[i];
				cnt++;
			}
			
			tot*=cnt;
		}
	}
	
	if(n>1) {
		tot*=2;
	}
	
	return tot;
}
void task()
{
    //code here...
    
    ll n, ans=0, mid;
    
    cin >> n;
    
    sieve((int)sqrt(n+1));
    
    for(ll K=1; K<=n; K++){
		mid = n/K;
		ans += K*mid*(mid+1)/2;
	}
	
	cout << ans << "\n";
}

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

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    task();

    return 0;
}




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

int64_t lucas(int n) {
  if(n == 0)
    return 2;
  else if (n == 1)
    return 1;
  else
    return lucas(n-1) + lucas(n-2);
}

int main() {
  int N;
  cin >> N;
  vector<int64_t> lc(N+1);
  
  lc.at(0) = 2;
  lc.at(1) = 1;
  for(int i=2; i<=N; i++)
    lc.at(i) = lc.at(i-1) + lc.at(i-2);
  
  cout << lc.at(N) << endl;
}

Measured memory_bytes: 256
package main

// Solution for https://atcoder.jp/contests/abc075/tasks/abc075_a

import (
	"bufio"
	"fmt"
	"io"
	"os"
)

type contest struct {
	in  io.Reader
	out io.Writer
}

func (con *contest) Scan(a ...interface{}) (int, error) {
	return fmt.Fscan(con.in, a...)
}
func (con *contest) Scanln(a ...interface{}) (int, error) {
	return fmt.Fscanln(con.in, a...)
}
func (con *contest) Scanf(f string, a ...interface{}) (int, error) {
	return fmt.Fscanf(con.in, f, a...)
}
func (con *contest) Print(a ...interface{}) (int, error) {
	return fmt.Fprint(con.out, a...)
}
func (con *contest) Println(a ...interface{}) (int, error) {
	return fmt.Fprintln(con.out, a...)
}
func (con *contest) Printf(f string, a ...interface{}) (int, error) {
	return fmt.Fprintf(con.out, f, a...)
}
func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()
	con := &contest{in: in, out: out}
	con.main()
}

func (con *contest) main() error {
	var a, b, c int
	con.Scan(&a, &b, &c)
	x := 0
	if a == b {
		x = c
	}
	if b == c {
		x = a
	}
	if c == a {
		x = b
	}
	con.Println(x)
	return nil
}


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

int main() {
  int N, D;
  cin >> N >> D;
  int res;
  if (N%(2*D+1) == 0) res = N/(2*D+1);
  else res = N/(2*D+1)+1;
  cout << res << endl;
}


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

using namespace std;

int main(){
  long long int n;
  cin >> n;
  vector<long long int> h;
  for(int i = 0;i < n;i++){
    long long int a;
    cin >> a;
    h.push_back(a);
  }
  if(n == 1){
    cout << "Yes" << endl;
    return 0;
  }
  long long int max = h[0];
  for(long long int i = 1;i < n;i++){
    if(h[i-1] < h[i]){
      max = h[i]-1;
    }
    if(max > h[i]){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}


Measured memory_bytes: 1400
#include<bits/stdc++.h>
#define REP(i,n)for(int i=0;i<n;i++)
#define FORD(i,a,b) for(int i=a;i>=(b);i--)
#define MP make_pair
#define F first
#define S second
typedef long long ll;
using namespace std;
int main(){
//入力の高速化用のコード
    ll n,k,s,t;cin >> n >> k >> s >> t;
    vector<ll> b(n);REP(i,n)cin >> b[i];
    vector<ll> a;
    REP(i,n){
        bool f=true;
        REP(j,18){
            if((s>>j)&1 and !((b[i]>>j)&1)){
                f=false;break;
            }
            if(!((t>>j)&1) and (b[i]>>j)&1){
                f=false;break;
            }
        }
        if(f)a.push_back(b[i]);
    }
    n=a.size();
    k=min(n,k);
    vector<map<pair<ll,ll>,ll>> dp(k);
    REP(i,n){
        FORD(j,k-2,0){
            for(auto l=dp[j].begin();l!=dp[j].end();l++){
                dp[j+1][MP((l->F.F)&a[i],(l->F.S)|a[i])]+=(l->S);
            }
        }
        dp[0][MP(a[i],a[i])]=1;
    }
    ll ans=0;
    REP(i,k)ans+=(dp[i][MP(s,t)]);
    cout << ans << endl;
}

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

int main()
{
     string str;
     while (cin >> str) {
          string res;
          for (int i = 0; i < str.size(); i++) {
               if (str[i] != '@') res += str[i];
               else {
                    int tmp = str[i + 1] - '0';
                    for (int j = 0; j < tmp; j++) {
                         res += str[i + 2];
                    }
                    i += 2;
               }
          }
          cout << res << endl;
     }

     return 0;
}

Measured memory_bytes: 1184
N,K=map(int,input().split())
a=list(map(int,input().split()))
b=[0]*(int(2e5+1))
for i in range(N):
    b[a[i]]+=1
b.sort()
l=len(list(set(a)))
ans=0
for i in range(len(b)):
    if l<=K:
        print(ans)
        break
    else:
        if b[i]!=0:
            ans+=b[i]
            l-=1

Measured memory_bytes: 26812
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	r := bufio.NewReader(os.Stdin)

	var n, m, k int
	fmt.Fscanf(r, "%d %d %d\n", &n, &m, &k)

	g := make([]string, n)
	for i := 0; i < n; i++ {
		fmt.Fscanf(r, "%s\n", &g[i])
	}

	ans := int(1e9)
	for mask := uint(0); mask < (1 << uint(n-1)); mask++ {
		var delims []int
		for i := 0; i < n-1; i++ {
			if (mask & (1 << uint(i))) != 0 {
				delims = append(delims, i)
			}
		}
		delims = append(delims, n-1)

		blocks := make([]int, len(delims))
		last := -1
		count := len(delims) - 1
		ok := true
		for j := 0; j < m && ok; j++ {
			cur := 0
			rep := false
			for i := 0; i < n && ok; i++ {
				if i > delims[cur] {
					cur++
				}
				if g[i][j] == '1' {
					blocks[cur]++
				}
				if blocks[cur] > k {
					if j-1 == last {
						ok = false
					} else {
						rep = true
						break
					}
				}
			}
			if rep {
				count++
				last = j - 1
				for x, _ := range blocks {
					blocks[x] = 0
				}
				j--
			}
		}
		if ok {
			ans = min(ans, count)
		}
	}

	fmt.Println(ans)
}

func min(a, b int) int {
	if a <= b {
		return a
	}
	return b
}


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

using LL = long long;

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

  int ans;
  int a, b;
  cin >> a >> b;

  ans = a - 1;
  if (b >= a) {
    ans++;
  }

  cout << ans << '\n';

  return 0;
}

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

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#define boost ios::sync_with_stdio(0); cin.tie(0);
#define int long long

const int N = 1e5 + 10;
const int MOD = 1e9 + 7;

int32_t main(){
    boost;
    //code
    int a , b;
    char c;

    cin >> a >> c >> b;

    cout << ( c == '+' ? (a+b) : (a-b)); 
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll>
#define lque queue<ll>
#define lpque priority_queue<ll>
#define dlpque priority_queue<ll,lvector,greater<ll>>
#define P pair<ll,ll>
#define ALL(a) (a).begin(),(a).end()
#define rep(i,n) for(ll (i)=0; (i)<(n); ++(i))
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;cin>>s;
  ll l=s.length();
  map<ll,ll> mp;rep(i,l) mp[s[i]-'a']++;
  ll ans=l*(l-1)/2;
  for(auto e:mp) ans-=e.second*(e.second-1)/2;
  print(ans+1);
  return 0;
}

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

#define rep(i,n) for(ll i=0;i<(n);++i)
using ll = int_fast64_t;
using pll = pair<ll,ll>;
constexpr ll INF = 1LL<<60;
constexpr ll MOD = 1e9+7;
template<class T> bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T> bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}return 0;}
#if loc||local
void dump(){cerr<<endl;}
template<class T,class... Ts> void dump(T&& h, Ts&&... t){cerr<<h<<", ";dump(forward<Ts>(t)...);}
#else
void dump(){}
template<class T,class... Ts> void dump(T&& h, Ts&&... t){}
#endif
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T> ostream &operator<<(ostream& os,vector<T>const& v){for(auto const& vi:v)os<<vi<<" ";return os;}
template<class T,class U> ostream &operator<<(ostream& os,pair<T,U>const& p){os<<p.first<<","<<p.second;return os;}
template<class T>vector<T> vec(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto vec(size_t a, Ts... ts){return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...));}
using T3 = tuple<ll,ll,ll>;
using T4 = tuple<ll,ll,ll,ll>;

signed main(){

  int n;
  cin>>n;
  vector<ll> a(n);
  cin>>a;
  vector<vector<int>> adj(n);
  rep(i,n-1){
    int u,v;
    cin>>u>>v;
    u--;v--;
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
  }

  vector<int> ans(n);
  auto dfs = [&](auto&& dfs,vector<ll>& lis,int cur,int prv)->void{
    auto itr = lower_bound(lis.begin(),lis.end(),a[cur]);
    ll val = *itr;
    *itr = a[cur];
    ans[cur] = lower_bound(lis.begin(),lis.end(),INF)-lis.begin();
    for(auto& nxt:adj[cur]){
      if(nxt==prv)continue;
      dfs(dfs,lis,nxt,cur);
    }
    *itr = val;
  };
  vector<ll> lis(n+1,INF);
  dfs(dfs,lis,0,-1);
  for(auto a:ans)cout<<a<<endl;

}

Measured memory_bytes: 32404
import java.util.*;

public class Main {

    static final int D = 365;
    static final int[] c = new int[27];
    static final int[][] s = new int[365][27];
    static final int[] ans = new int[365];
    static final int[] last = new int[27];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int d = sc.nextInt();
        int fla = 0;
        for (int i = 1; i <= 26; i++) {
            c[i] = sc.nextInt();
            fla += c[i];
        }
        for (int i = 0; i < D; i++) {
            for (int j = 1; j <= 26; j++) {
                s[i][j] = sc.nextInt();
            }
        }
        Map<Integer, TreeSet<Integer>> lastMap = new HashMap<>();
        for (int i = 1; i <= 26; i++) {
            lastMap.put(i, new TreeSet<>());
            lastMap.get(i).add(0);
            lastMap.get(i).add(D+1);
        }
        StringBuilder sb = new StringBuilder();
        int score = 0;
        for (int i = 0; i < D; i++) {
            score -= fla;
            int max = score;
            int idx = 0;
            for (int j = 1; j <= 26; j++) {
                int tmp = score + s[i][j] +  c[j] *(i - last[j] + 1);
                if(max < tmp){
                    max = tmp;
                    idx = j;
                }
            }
            score = max;
            ans[i] = idx;
            last[idx] = i+1;
            lastMap.get(idx).add(i+1);
        }

        for (int i = 0; i < D; i++) {
            int prei = ans[i];
            int idx = prei;
            int max = s[i][prei] + c[prei] * (i - lastMap.get(prei).lower(i+1) +1) * (lastMap.get(prei).higher(i+1) - i -1);
            for (int j = 1; j <= 26; j++) {
                if(j == prei)continue;
                int tmp = s[i][j] + c[j] * (i - lastMap.get(j).lower(i+1) +1) * (lastMap.get(j).higher(i+1) - i -1);
                if(max < tmp){
                    idx = j;
                    max = tmp;
                }
            }
            if(prei != idx){
                ans[i] = idx;
                lastMap.get(prei).remove(i+1);
                lastMap.get(idx).add(i+1);
            }
        }


        for (int i = 0; i < D; i++) {
            sb.append(ans[i] + "\n");
        }
        System.out.print(sb.toString());
        sc.close();

    }

}


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

using namespace std;
const int MAX = 2e5 + 5;
typedef long long ll;

int h[MAX], a[MAX];
ll dp[MAX];

void max_self(ll &a, ll b)
{
    a = max(a, b);
}

int main()
{
    int n;

    cin >> n;

    for(int i = 0; i < n; i++)
        cin >> h[i];

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

    int base = 1;

    while(base <= n)
        base *= 2;

    vector<ll>tree(base * 2);

    for(int flower = 0; flower < n; flower++)
    {
        int nod = base + h[flower];
        ll best = 0;

        while(nod > 1)
        {
            if(nod % 2 == 1)
                max_self(best, tree[nod - 1]);

            nod /= 2;
        }

        dp[h[flower]] = best + a[flower];

        for(int nod = base + h[flower]; nod; nod /= 2)
            max_self(tree[nod], dp[h[flower]]);
       /* for(int j = 0; j < h[i]; j++)
            max_self(dp[h[i]], dp[j] + a[i]);*/
    }

    ll sol = 0;

    for(int i = 0; i < n; i++)
        max_self(sol, dp[h[i]]);

    cout << sol;

    return 0;
}


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


int main(){
  string S;
  cin >> S;
  
  if ((S.at(0) == S.at(1)) && (S.at(1) == S.at(2))) {
    cout << "Yes" << endl;
    return 0;
  }
  else if ((S.at(2) == S.at(3)) && (S.at(1) == S.at(2))) {
    cout << "Yes" << endl;
    return 0;
  }
  else {
    cout << "No" << endl;
    return 0;
  }
}


Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main {
    public static final long mod = (long)1e9+7;
    public static final long INF = Long.MAX_VALUE/10;
    public static final int inf = Integer.MAX_VALUE/10;

    static void solve(InputReader in, PrintWriter out){
        int n = in.ni(), x, y, h;
        pair sp = new pair();
        pair[] p = new pair[n];
        boolean start = true;
        for (int i = 0; i < n; i++) {
            x = in.ni(); y = in.ni(); h = in.ni();
            if(start&&h!=0){
                sp.x = x; sp.y = y; sp.h = h;
                start  = false;
            }
            p[i] = new pair();
            p[i].x = x; p[i].y = y; p[i].h = h;
        }
        out:for (int i = 0; i <= 100; i++) {
            for (int j = 0; j <= 100; j++) {
                h = sp.h+Math.abs(sp.x-i)+Math.abs(sp.y-j);
                boolean flag = true;
                for(pair a: p){
                    int H = h-Math.abs(a.x-i)-Math.abs(a.y-j);
                    if(H>0&&H!=a.h || H<=0&&a.h!=0){
                        flag = false;
                        break;
                    }
                }
                if(flag){
                    out.printf("%d %d %d", i, j, h);
                    break out;
                }
            }
        }
    }
    public static class pair{ int x, y, h;}
    public static void main(String[] args) throws Exception{
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        solve(in, out);
        out.close();
    }
    public static class InputReader{
        private BufferedReader br;
        private StringTokenizer st;
        public InputReader(InputStream is){
            br = new BufferedReader(new InputStreamReader(is));
            st = null;
        }
        public String ns(){
            if(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (Exception e){
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }
        public long nl(){
            return Long.parseLong(ns());
        }
        public int ni(){
            return Integer.parseInt(ns());
        }
        public Double nd(){
            return Double.parseDouble(ns());
        }
        public int[] ni(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }
        public long[] nl(int n){
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nl();
            }
            return a;
        }
        public double[] nd(int n){
            double[] a = new double[n];
            for (int i = 0; i < n; i++) {
                a[i] = nd();
            }
            return a;
        }
    }
}

Measured memory_bytes: 23508
#include<stdio.h>

int main(void){
	int a, b, c, d, n, count;

	while (scanf("%d", &n) != EOF) {
		count = 0;

		if (n > 50)
			break;

		for (a = 0; a < 10; a++) {
			for (b = 0; b < 10; b++) {
				for (c = 0; c < 10; c++) {
					for (d = 0; d < 10; d++) {
						if (a + b + c + d == n) {
							count++;
						}
					}
				}
			}
		}

		printf("%d\n", count);
	}
	return 0;
}

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

typedef long int lint;
typedef long long int llint;
typedef pair<int, int> pii;
typedef pair<int, string> pis;
typedef pair<long, long> pll;

#define EACH(i, c) for (__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define ALL(c) (c).begin(), (c).end()
#define FOR(i, s, e) for (int i = (s); i < (int)(e); ++i)
#define REP(i, n) FOR(i, 0, n)
#define endl '\n'
#define mod 1000000007
#define INF 100000000
#define fk first
#define sv second

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

template<typename T>
void print(const std::vector<T>& v, char sep=' ') {
  for (int i = 0; i < (int)v.size(); i++) {
    if (i != 0) cout << sep;
    cout << v[i];
  }
  cout << endl;
}

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

  cin >> n;
  int a[n + 1];
  bool f[n + 1];
  REP(i, n) {
    cin >> a[i + 1];
    f[i + 1] = false;
  }

  int pos, ct;
  pos = ct = 0;
  pos++;
  while (true) {
    if (pos == 2) {
      cout << ct << endl;
      break;
    }
    if (f[pos]) {
      cout << "-1" << endl;
      break;
    }
    f[pos] = true;
    pos = a[pos];
    ct++;
    
  }


}

Measured memory_bytes: 768
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int a[]=new int[n];
		long b[]=new long[n+2];
		long s=0;
		for(int i=0;i<n;i++){
			a[i]=sc.nextInt();
			b[a[i]]++;
		}
		for(int i=0;i<=n;i++)s+=b[i]<2?0:b[i]*(b[i]-1)/2;
		for(int i=0;i<n;i++)System.out.println(s-b[a[i]]+1);
	}
}


Measured memory_bytes: 95144
def main():
    n = int(input())
    a_lst = list(map(int, input().split()))
    is_ok = True

    for a in a_lst:
        if a % 2 == 0:
            if a % 3 != 0 and a % 5 != 0:
                is_ok = False

    if is_ok:
        ans = "APPROVED"
    else:
        ans = "DENIED"

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 61728
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>
#include <string.h>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()

typedef long long lint;

using namespace std;

int main(){
  int N,K;
  cin>>N>>K;
  cout<<N-K+1<<endl;
  return 0;
}


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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using edge = pair<ll, P>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
using Graph = vector<vector<ll>>;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

#include "cpp-pyprint/pyprint.h"

#endif

void Main() {
    string S, T;
    cin >> S >> T;
    int ans = 0;
    rep(i, 3){
        ans += S[i] == T[i];
    }
    cout << ans << endl;

}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
}


Measured memory_bytes: 256