akhauriyash/Code-Regression huggingface dataset:
import std.algorithm;
import std.array;
import std.container;
import std.conv;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void scan(T...)(ref T a) {
    string[] ss = readln.split;
    foreach (i, t; T) a[i] = ss[i].to!t;
}
T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

long calc(long n) {
    long ans = n - 1;
    for (long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            long x = n / i;
            ans = min(ans, (i - 1) + (x - 1));
        }
    }
    return ans;
}

void main() {
    long n = read!long;
    writeln(calc(n));
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<math.h>
#include<iomanip>
#include<stdio.h>
#include<cstring>
using namespace std;
 
int main(){

  int n, a, b, ans=0;
  cin >> n >> a >> b;

  for(int i=1; i<=n; i++){
    int c=0, t=i;
    for(int j=0; j<5; j++){
      c+=t%10;
      t/=10;
    }
    if(a<=c && c<=b){
      ans+=i;
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
import java.util.*;
//import java.util.Math.*;

public class Main {
    public static void main(String[] args) throws Exception {

    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int A[] = new int[n];
    int i;
    boolean flag = true;
    int tmp;
    int count = 0;
    
    for(i = 0; i < n; i++){
        A[i] = sc.nextInt();
    }
    
    while(flag){
        flag = false;
        for(i = n-1; i > 0; i--){
            if(A[i] < A[i-1]){
                tmp = A[i-1];
                A[i-1] = A[i];
                A[i] = tmp;
                flag = true;
                //System.out.println("test");
                count++;
            }
        }
    }
    
    for(i = 0; i < n; i++){
        System.out.print(A[i]);
        if(i < (n-1)){ System.out.print(" "); }
    }
    System.out.println();
    System.out.println(count);

    }
}



Measured memory_bytes: 26324
#include<stdio.h>
#define N 10000
typedef struct{
  int p;
  int left;
  int right;
}Node;
Node tary[N];
int n;

void pre(int value){
  if(value==-1)return;
  printf(" %d",value);
  pre(tary[value].left);
  pre(tary[value].right);
}

void in(int value){
  if(value==-1)return;
  in(tary[value].left);
  printf(" %d",value);
  in(tary[value].right);
}
void post(int value){
  if(value==-1)return;
  post(tary[value].left);
  post(tary[value].right);
  printf(" %d",value);
}
int main(){
  int i,v,left,right,r;
  scanf("%d",&n);
  for(i=0;i<n;i++){tary[i].p=-1;}

  for(i=0;i<n;i++){
    scanf("%d%d%d",&v,&left,&right);
    tary[v].left=left;
    tary[v].right=right;
    if(left!=-1)tary[left].p=v;
    if(right!=-1)tary[right].p=v;
  }
  for(i=0;i<n;i++){
    if(tary[i].p==-1)r=i;
  }
  printf("Preorder\n");
  pre(r);
  printf("\n");
  printf("Inorder\n");
  in(r);
  printf("\n");
  printf("Postorder\n");
  post(r);
  printf("\n");
  return 0;
}
    



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

#define int long long

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

int N, K, L;
int par_K[200000], rank_K[200000];
int par_L[200000], rank_L[200000];
pair<int, int> finds[200000];
map<pair<int, int>, int> ans_map;

void init(int n, int par[], int rank[]) {
    for (int i = 0; i < n; i++) {
        par[i] = i;
        rank[i] = 0;
    }
}

int find(int x, int par[]) {
    if (par[x] == x) {
        return x;
    } else {
        return par[x] = find(par[x], par);
    }
}

void unite(int x, int y, int par[], int rank[]) {
    x = find(x, par);
    y = find(y, par);
    if (x == y) {
        return;
    }
    if (rank[x] < rank[y]) {
        par[x] = y;
    } else {
        par[y] = x;
        if (rank[x] == rank[y]) {
            rank[x]++;
        }
    }
}

signed main() {
    cin >> N >> K >> L;
    init(N, par_K, rank_K);
    init(N, par_L, rank_L);
    for (int i = 0; i < K; i++) {
        int p, q;
        cin >> p >> q;
        unite(p - 1, q - 1, par_K, rank_K);
    }
    for (int i = 0; i < L; i++) {
        int r, s;
        cin >> r >> s;
        unite(r - 1, s - 1, par_L, rank_L);
    }
    for (int i = 0; i < N; i++) {
        ans_map[make_pair(find(i, par_K), find(i, par_L))]++;
    }
    for (int i = 0; i < N; i++) {
        cout << ans_map[make_pair(find(i, par_K), find(i, par_L))] << " ";
    }
    cout << endl;


    return 0;
}


Measured memory_bytes: 19328
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,a,b) for(int i =(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
#define REPm(i,n) for(int i=(n)-1;i>=0;i--)
#define REP1(i,n) for(int i=1;i<=(n);i++)
typedef long long ll;
int main(){
    int N;
    cin >> N;
    int Amax = 0;
    int Bmin = 1e9;
    REP(i,N){
        int A,B;
        cin >> A >> B;
        if(Amax < A){
            Amax = A;
            Bmin = B;
        }
    }
    cout << Amax+Bmin << endl;
    return 0;
}


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

typedef long long int ll;
typedef vector<long long>lve;
typedef vector<pair<ll,ll> > lvp;
typedef vector<pair<string,ll> > svp;

#define endl       '\n'
#define F          first
#define S          second
#define pp         pop_back
#define PI         2*acos(0)
#define pb         push_back
#define mp         make_pair
#define GCD(x,y)   __gcd(x,y)
#define lb         lower_bound
#define up         upper_bound
#define bs         binary_search
#define For(i,j,k) for(i=j;i<k;i++)
#define FOR(i,j,k) for(i=j;i>=k;i--)
#define LCM(x,y)   ((x*y)/__gcd(x,y))
#define btpc       __builtin_popcountll
#define sp(x)      cout<<fixed<<setprecision(x)

const   long long  cs=2e5+5;
const   long long  inf=1e18;
const   long long  mod=1e9+7;
int main()
{	
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);    cout.tie(NULL);
  
    ll t,n,m,a,b,c,d,e,i,j,k,x,y,z,cnt=0;
    bool flag = false;
    
    vector<double>v;
    vector<double>::iterator low,upp;
    cin>>n>>k;
    For(i,0,n)
    {
    	cin>>a>>b;
    	v.pb(sqrt(a*a+b*b));
    }
    sort(v.begin(),v.end());
    upp=up(v.begin(),v.end(),k);
    cout<<upp-v.begin()<<endl;

    return 0;
}

Measured memory_bytes: 5340
import java.util.*; 

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

  		int[] a1=new int[n+1];
  		int[] a2=new int[n+1];
        a1[0]=0;
  		a2[0]=0;
		for(int c=1;c<n+1;c++){
    		a1[c]=a1[c-1]+sc.nextInt();
    	}
  		for(int c=1;c<n+1;c++){
    		a2[c]=a2[c-1]+sc.nextInt();
    	}
  		int max=0;
    
 	for(int d=1;d<n+1;d++){
       max=Math.max(max,a1[d]-a1[0]+a2[n]-a2[d-1]);
    }

    	System.out.println(max);
    }
}


Measured memory_bytes: 36052
#include <iostream>
#include <cstdlib>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
	int N, Q, T;
	string Name;
	cin >> N >> Q;
	queue<pair<string, int> > q;
	for (int i = 0; i < N; i++) {
		cin >> Name >> T;
		q.push(make_pair(Name, T));
	}

	pair<string, int>P;
	int a = 0, b = 0;
	while (!q.empty()) {
		P = q.front(); q.pop();
		b = min(P.second, Q);
		P.second -= b;
		a += b;
		if (P.second > 0) {
			q.push(P);
		} else {
		    cout << P.first << " " << a << endl;
		}
	}
}



Measured memory_bytes: 6376
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <numeric>
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define mod 1000000007
typedef long long ll;
using namespace std;

ll dp[101000][13];

int main(){
  string S;
  cin >> S;
  int N = (int)S.size();
  ll ans;
  if(S[0]=='?'){
    rep(i,10){
      dp[0][i] = 1;
    }
  }
  else{
    dp[0][(int)(S[0]-'0')]=1;
  }
  rep(i,N-1){
    if(S[i+1]=='?'){
      rep(d,10) {
        rep(j,13) {
          dp[i+1][(j*10+d)%13] += dp[i][j];
          dp[i+1][(j*10+d)%13] %= mod;
        }
      }
    }
    else{
      int digit = (int)(S[i+1]-'0');
      rep(j,13) {
        dp[i+1][(j*10+digit)%13] += dp[i][j];
        dp[i+1][(j*10+digit)%13] %= mod;
      }
    }
  }

  ans = dp[N-1][5];
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 10752
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int modecnt = 0;
    map<int, int> m;
    int n;
    while(cin >> n) 
        modecnt = max(modecnt, ++m[n]);

    vector<int> ans;
    for(map<int,int>::iterator it = m.begin(); it != m.end(); ++it)
        if(it->second == modecnt) ans.push_back(it->first);
    sort(ans.begin(), ans.end());
    for(int i = 0; i < ans.size(); ++i)
        cout << ans[i] << endl;

    return 0;
}

Measured memory_bytes: 0
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <limits>
#include <numeric>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <stack>

using namespace std;

#define INFint (1<<30)
#define BOUND 27182818284
#define MAT 2

typedef long long ll;
typedef long long int lli;
typedef pair<ll, ll> P;

ll MOD = 1000000007;
const ll INF = (1ll<<60);
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for(int i=int(a);i<int(b);++i)

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

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

// gcd
template<typename T>
T gcd(T a, T b) {
    if (a == 0)
        return b;
    return gcd(b % a, a);
}

int findGCD(vector<int> arr) {
    int result = arr[0];
    for (auto a: arr) {
        result = gcd(a, result);
    }
    return result;
}

template<typename T>
T lcm(T m, T n) {
    // 引数に0がある場合は0を返す
    if ((0 == m) || (0 == n))
        return 0;
    return ((m / gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
    fill((T *) array, (T *) (array + N), val);
}


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

// v.front() = -BOUND;
// v.back() = BOUND;

//struct edge{
//    int cost, to;
//
//    edge(int in_cost, int in_to){
//        cost=in_cost;
//        to=in_to;
//    }
//    bool operator<(const edge &a) const
//    {
//        return cost > a.cost;
//    }
//};

map<pair<int,int>,int>mp;
int main() {
    int N; cin >> N;
    vector<int>v[110000];
    vector<int>A(N), B(N);
    rep(i,N-1){
        int a,b; cin >> a >> b;
        a--, b--;
        A[i]=a, B[i]=b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    int hasColor=0;
    int not_allow_use[120000];
    int used[120000];
    Fill(used, false);
    not_allow_use[0]=0;
    queue<int>q; q.push(0);
    used[0]= true;
    int max_color=0;
    while(!q.empty()){
        int now_node = q.front();
        used[now_node]=true;
        q.pop();
        int color=1;
        for(auto a: v[now_node]){
            if(used[a])
                continue;
            else{
                q.push(a);
            }
            if(not_allow_use[now_node] != color){
                mp[pair<int,int>(now_node, a)]=color;
                mp[pair<int,int>(a, now_node)]=color;
                not_allow_use[a]=color;
            }else{
                color++;
                mp[pair<int,int>(now_node, a)]=color;
                mp[pair<int,int>(a, now_node)]=color;
                not_allow_use[a]=color;
            }
            max_color = max(max_color,color);
            color++;
        }
    }

    cout << max_color << endl;
    rep(i,N-1){
        cout << mp[pair<int,int>(A[i], B[i])] << endl;
    }
    return 0;
}


Measured memory_bytes: 17280
<?php
while (fscanf(STDIN, "%d", $n) == 1)
{
	$cnt = 0;
	for ($i = 0; $i < 10; $i++)
		for ($j = 0; $j < 10; $j++)
			for ($k = 0; $k < 10; $k++)
				for ($l = 0; $l < 10; $l++)
					if ($i+$j+$k+$l == $n)
						$cnt++;
	printf("%d\n", $cnt);
}

Measured memory_bytes: 15208
#!/usr/bin/env python3
from collections import deque

INF = 10**9
k = int(input())

# (辺の伸びる先, コスト)
G = [((10 * i % k, 0), ((i + 1) % k, 1)) for i in range(k)]
s = 1

# 01 - BFS
dist = [INF] * k
S = deque([s])
T = deque()
dist[s] = 0

d = 0
while S:
    while S:
        v = S.popleft()
        for w, c in G[v]:
            if d + c < dist[w]:
                dist[w] = d + c
                if c:
                    T.append(w)
                else:
                    S.append(w)
    S, T = T, S
    d += 1

print(dist[0] + 1)

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

namespace ConsoleApp2
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int y = int.Parse(Console.ReadLine());

            int n2 = n / 500;
             n = n - n2 * 500;
            if (n <= y)
            {
                Console.WriteLine("Yes");
            } else
            {
                Console.WriteLine("No");
            }
            //Console.ReadLine();
        }
    }
}


Measured memory_bytes: 13140
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long count = 2;
        double lim = Math.sqrt(n);
        long ins = 0;
        int ans = 0;
        while (n!=1&&count<=lim){
            if (n%count==0){
                n/=count;
                ins++;
            } else if (ins!=0){
                int c = 0;
                int i = 1;
                while (c+i<=ins){
                    c+=i;
                    i++;
                }
                ans+=i-1;
                ins=0;
                if (count==2)count--;
                count+=2;
            }else {
                if (count==2)count--;
                count+=2;
            }
        }
        if (ins!=0){
            int c = 0;
            int i = 1;
            while (c+i<=ins){
                c+=i;
                i++;
            }
            ans+=i-1;
        }
        if (n!=1)ans++;
        System.out.println(ans);
    }
}


Measured memory_bytes: 35448
use std::io;
use std::str::FromStr;

fn input_int_tuple() -> (i32, i32) {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line);
    let vec: Vec<i32> = line.split_whitespace().map(|s| s.parse().unwrap()).collect();
    (vec[0], vec[1])
}

fn main() {
    let (a, b) = input_int_tuple();
    if (b - 1) % (a - 1) == 0 {
        println!("{}", (b - 1) / (a - 1));
    } else {
        println!("{}", (b - 1) / (a - 1) + 1);
    }
    
}


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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  ll total;
  ll m1 = 0;
  total = accumulate(a.begin(), a.end(), 0);
  for (int i=0; i<n; i=i+2) {
    m1 += 2 * a[i];
  }
  m1 -= total;
  vector<int> ans(n);
  ans[0] = m1;
  for (int i=1; i<n; i++){
    ans[i] = 2 * (a[i-1] - ans[i-1] / 2);
  }
  rep(i,n) printf("%d%c", ans[i], i==n-1?'\n':' ');
  return 0;
}


Measured memory_bytes: 2048
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

#define vi vector<int>
#define vl vector<long long>
#define vvi vector< vector<int> >
#define vvl vector< vector<ll> >
#define vp vector<P>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPD(i, n) for (int i = (int)(n-1); i >= 0; i--)
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define FORD(i, a, b) for (int i = (int)(a); i >= (int)(b); i--)
#define INF 1e18
#define INFTY 1e9
const int mod = 1000000007;
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))

template<class T> bool chmax(T &a, const T & b) {
    if (a<b) {
        a = b;
        return true;
    }
    return false;
}

template<class T> bool chmin(T &a, const T & b) {
    if (a>b) {
        a = b;
        return true;
    }
    return false;
}

//cout << fixed << setprecision(10) << y << endl;
struct edge {int to, cost;};
vector< vector<edge> > es;
const int MAX_N = 10010;

int gcd(int a, int b) {
    if (b > a) {
        int c = b;
        b = a;
        a = c;
    }
    int r = a % b;
    if (r == 0) return b;
    return gcd(b, r);
}

ll lcm(ll a, ll b) {
    return a/gcd(a, b)*b;
}

int main() {
    string s, t;
    cin >> s;
    cin >> t;
    int n = s.length();
    int m = t.length();
    int dp[n+1][m+1];
    REP(i, n+1) {
        dp[i][0] = 0;
    }
    REP(j, m+1) {
        dp[0][j] = 0;
    }
    REP(i, n) {
        REP(j, m) {
            dp[i+1][j+1] = dp[i][j];
            if (s[i] == t[j]) dp[i+1][j+1] += 1;
            else chmax(dp[i+1][j+1], max(dp[i+1][j], dp[i][j+1]));
        }
    }
    int i = n-1;
    int j = m-1;
    string res = "";
    while (i >= 0 && j >= 0) {
        if (s[i] == t[j]) {
            res.push_back(s[i]);
            --i;
            --j;
        } else {
            if (dp[i+1][j] > dp[i][j+1]) {
                --j;
            } else {
                --i;
            }
        }
    }
    string ans = "";
    int l = res.length();
    REP(i, l) {
        ans.push_back(res[l-1-i]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 35456
import java.util.Scanner;

public class Main{
  public static void main(String[] args){
    Scanner scanner = new Scanner(System.in);
    long N = scanner.nextLong();
    long M = scanner.nextLong();
    long count = 0;

    if (N == 1 && M ==1){
      count = 1;
    }
    if (N == 1 && M > 1){
      count = M - 2;
    }
    if (N > 1 && M == 1){
      count = N - 2;
    }
    if (N > 1 && M > 1){
      count = (N - 2) * (M - 2);
    }
    System.out.println(count);
  }
}


Measured memory_bytes: 21716
from collections import deque

n=int(input())
a=list(map(int,input().split()))

ans=deque()
if n%2==0:
  for i in range(n):
    if i%2==0:
      ans.append(a[i])
    else:
      ans.appendleft(a[i])
else:
  for i in range(n):
    if i%2==0:
      ans.appendleft(a[i])
    else:
      ans.append(a[i])

print(*ans)

Measured memory_bytes: 25412
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
    char s[11], t[12];
    cin >> s >> t;
    for (long unsigned int i = 0; i < strlen(s); ++i) {
        if (s[i] != t[i]) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


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

int main() {
	string A, B;
	cin >> A >> B;
	int N, M;
	N = A.size();
	M = B.size();
	if (N > M)
		cout << "GREATER" << endl;
	else if (N < M)
		cout << "LESS" << endl;
	else {
		bool finished = false;
		for (int i = 0; i < N; i++) {
			if (A.at(i) > B.at(i)) {
				cout << "GREATER" << endl;
				finished = true;
				break;
			}
			else if (A.at(i) < B.at(i)) {
				cout << "LESS" << endl;
				finished = true;
				break;
			}
		}
		if (finished == false)
			cout << "EQUAL" << endl;
	}
}

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

#define pb push_back
#define F first
#define S second

#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define int long long
#define ll long long


	
void solve(){
	int n;
	cin >> n;
	int a[n];
	int dp[n + 1][3];
	memset(dp, 0, sizeof dp);
	for(int i = 1 ; i <= n ; i++){
		int x, y, z;
		cin >> x >> y >> z;
		dp[i][0] = max(dp[i - 1][1] + x, dp[i - 1][2] + x); 
		dp[i][1] = max(dp[i - 1][0] + y, dp[i - 1][2] + y); 
		dp[i][2] = max(dp[i - 1][0] + z, dp[i - 1][1] + z); 
	}	
	cout << max({dp[n][0], dp[n][1], dp[n][2]});
}

signed 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: 2560
#include <iostream>
#include <iomanip>
#include <math.h>
#include <string>
#include <algorithm>
//#include <ctype.h>
#include <vector>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <bitset>
using namespace std;

#define ll long long int
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repm(i, a, n) for (int i = a; i >= n; i--)
#define INF 1e9
#define LINF 1e17
#define MOD (int)(1e9 + 7)
#define pi 3.141592653589
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vs vector<string>
#define vii vector<vector<int>>
#define vll vector<ll>
#define vllll vector<vector<ll>>
#define ALL(a) (a).begin(), (a).end()
#define sort_v(a) sort(a.begin(), a.end())
#define fi first
#define se second

void print(bool c)
{
    if (c)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

void Print(bool c)
{
    if (c)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

ll gcdll(ll a, ll b)
{
    while (1)
    {
        if (a < b)
            swap(a, b);
        if (b == 0)
            break;
        a %= b;
    }
    return a;
}

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

bool cmp(const pii &a, const pii &b)
{
    if (a.second != b.second)
        return a.second < b.second;
    return a.first < b.first;
}

int setmode(int x, int y)
{
    if (x < y)
        return 0;
    if (x > y)
        return 1;
    if (x == y)
        return 2;
}

int main(void)
{
    int n;
    cin >> n;
    vll a(n);
    rep(i, 0, n) cin >> a[i];
    int ans = 0, mode = 0; //0->increase, 1->decrease 2->keep
    mode = setmode(a[0], a[1]);

    rep(i, 0, n - 1)
    {
        //cout << "mode=" << mode << endl;
        if ((a[i] >= a[i + 1] && mode == 1) || (a[i] <= a[i + 1] && mode == 0))
            continue;
        if (mode == 2)
        {
            mode = setmode(a[i], a[i + 1]);
            continue;
        }
        //cout << i << endl;
        ans++;
        mode = setmode(a[i + 1], a[i + 2]);
    }
    ans++;
    cout << ans << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    int a[26] = {0};
    for(int i = 0; i < s.size(); ++i) {
        a[s[i] - 'a'] = 1;
    }
    for(int i = 0; i < 26; ++i) {
        if(a[i] == 0) {
            cout << (char)(i+'a') << endl;
            return 0;
        }
    }
    cout << "None" << endl;

    return 0;
}

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

int main(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    int c = 1;
    for(int i = 1; i < s.size();i++){
       if(s[i] != s[i-1]) {
           c++;
       }
    }
    cout << c << endl;
    return 0;
}


Measured memory_bytes: 512
k,n = map(int,input().split())
a_list = list(map(int,input().split()))
re_a = []
for x in a_list:
    re_a.append(x-k)
a_list_add_re = re_a+a_list
result = []
x = n - 1
for i in range(len(a_list_add_re)-x):
    result.append(a_list_add_re[i+x] - a_list_add_re[i])
    
print(min(result))

Measured memory_bytes: 32368
// ※※※ 解答不能 ※※※
// I9992147氏.
// https://atcoder.jp/contests/keyence2020/submissions/9588989
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using P = pair<int, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second
#define all(x) x.begin(), x.end()
int d[202020], a[202020], b[202020], c[202020];
vi G[202020];

int main(){
    int N, M;
    map<P, int> mp;
    scanf("%d %d", &N, &M);
    repx(i, 1, N + 1) scanf("%d", &d[i]);
    repx(i, 1, M + 1){
        scanf("%d %d", &a[i], &b[i]);
        G[a[i]].pb(b[i]);
        G[b[i]].pb(a[i]);
    }
    vector<P> v;
    repx(i, 1, N + 1) v.pb({d[i], i});
    sort(all(v));
    rep(i, v.size()){
        int u = v[i].b, p = 0;
        if(c[u]) continue;
        for(auto v : G[u]){
            if(d[v] <= d[u]){
                p = v;
                break;
            }
        }
        if(!p){
            puts("-1");
            return 0;
        }
        if(!c[p]) c[p] = 1;
        c[u] = -c[p];
        mp[minmax(u, p)] = d[u];
    }
    repx(i, 1, N + 1) putchar(c[i] == 1 ? 'B' : 'W');
    puts("");
    repx(i, 1, M + 1) printf("%d\n", mp.count(minmax(a[i], b[i])) ? mp[minmax(a[i], b[i])] : 1000000000);
    return 0;
}

Measured memory_bytes: 20972
#include<cstdio>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;
#define MAXN 1000100
#define LL long long
int tot,vis[MAXN],n,ans;
LL prim[MAXN],a[MAXN+5],b[MAXN+5];
map<LL,int>cnt;
void Pre()
{
	for(int i=2;i<MAXN;i++)
	{
		if(!vis[i]) prim[tot++]=i;
		for(int j=0;prim[j]*i<MAXN;j++)
		{
			vis[i*prim[j]]=1;
			if(i%prim[j]==0) break;
		}
	}
}
void Solve(int i,LL x)
{
	a[i]=b[i]=1;
	for(int j=0;prim[j]*prim[j]*prim[j]<=x;j++)
	{
		int c=0;
		while(x%prim[j]==0) x/=prim[j],c++;
		if(c%3==1) a[i]*=prim[j],b[i]*=prim[j]*prim[j];
		else if(c%3==2) a[i]*=prim[j]*prim[j],b[i]*=prim[j];
	}
	if(x!=1)
	{
		LL k=sqrt(x);
		if(k*k==x) a[i]*=k*k,b[i]*=k;
		else
		{
			a[i]*=x,b[i]*=x*x;
			if(x>4000000000&&b[i]>0&&b[i]<10000000000LL)
			{
				printf("%lld %lld\n",a[i],b[i]);
			}
		}
	}
}
int main()
{
	Pre();
	scanf("%d",&n);
	LL x;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&x);
		Solve(i,x);
		cnt[a[i]]++;
	}
	for(int i=1;i<=n;i++)
	{
		if(cnt[a[i]]==0) continue;
		if(a[i]==b[i]) 	ans++,cnt[a[i]]=0;
		else ans+=max(cnt[a[i]],cnt[b[i]]),cnt[a[i]]=0,cnt[b[i]]=0;
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 24448
#!/usr/bin/env python3
import sys


def solve(D: int, N: int):
    n = N
    if n == 100:
        n = 101
    print(int((100**D)*n))


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

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

typedef long long LL;

const int MAXN = 100010;

int n, m, size, flag, cnt1, cnt2, cnt3, col[MAXN];
LL ans;
vector < int > G[MAXN];

inline void dfs(int x, int c)
{
	size++;
	col[ x ] = c;
	for( auto y : G[ x ] )
		if( col[ y ] == -1 ) dfs( y, c ^ 1 );
		else if( col[ y ] == c ) flag = 1;
}

int main()
{
#ifdef wxh010910
	freopen( "data.in", "r", stdin );
#endif
	scanf( "%d%d", &n, &m );
	memset( col, -1, sizeof col );
	for( int i = 1, x, y ; i <= m ; i++ ) scanf( "%d%d", &x, &y ), G[ x ].pb( y ), G[ y ].pb( x );
	for( int i = 1 ; i <= n ; i++ ) if( col[ i ] == -1 )
	{
		size = flag = 0;
		dfs( i, 0 );
		if( size == 1 ) cnt1++;
		else if( flag ) cnt2++;
		else cnt3++;
	}
	ans = 2LL * cnt1 * n - 1LL * cnt1 * cnt1;
	ans += 1LL * cnt2 * cnt2 + 2LL * cnt2 * cnt3 + 2LL * cnt3 * cnt3;
	cout << ans << endl;
	return 0;
}


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

int n, k;
int a[7][11];
int s, t;
int ans;

int main(){
	scanf("%d %d", &n, &k);
	a[0][0] = 4;
	for(int i=1; i<7; i++){
		a[i][0] = (a[i-1][0] + 9) % 11;
	}
	for(int i=0; i<7; i++){
		for(int j=1; j<11; j++){
			a[i][j] = (a[i][j-1] + 8) % 11;
		}
	}
	for(int i=5; i<7; i++){
		for(int j=0; j<11; j++){
			a[i][j] = 12;
		}
	}
	t = n % 11;
	s = (n - t) / 11 - 1;
	for(int i=0; i<7; i++){
		for(int j=0; j<11; j++){
			if(a[i][j] == k) ans++;
		}
	}
	ans *= s;
	for(int i=0; i<7; i++){
		for(int j=0; j<t-2+11; j++){
			int l = j % 11;
			if(a[i][l] == k) ans++;
		}
	}
	printf("%d\n", ans);
/*	
	printf("\n");
	printf("s=%d\tt=%d\n", s, t);
	for(int i=0; i<11; i++){
		for(int j=0; j<7; j++){
			printf("%d\t", a[j][i]);
		}
		printf("\n");
	}
*/	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,g;
cin>>n>>g;
long long int arr[n];
for(int i=0; i<n; ++i)
cin>>arr[i];
long long int sum(0);
sort(arr,arr+n);
for(int i=0; i<n-g; ++i)
sum+=(long long)arr[i];
cout<<sum;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const int INF = 1000000005;
const int MAX = 1000005;

int main() {
  vector<int> dp(MAX, INF), odddp(MAX, INF);
  dp[0] = 0;
  odddp[0] = 0;
  for (int i = 1;; ++i) {
    int w = i * (i+1) * (i+2) / 6;
    if (w >= MAX) break;
    FOR(j, w, MAX) {
      dp[j] = min(dp[j], dp[j-w] + 1);
      if (w & 1) odddp[j] = min(odddp[j], odddp[j-w] + 1);
    }
  }

  int n;
  while (cin >> n) {
    if (n == 0) break;
    cout << dp[n] << " " << odddp[n] << endl;
  }

  
  return 0;
}


Measured memory_bytes: 10492
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define Max(a, b) (a > b ? a : b)
#define Min(a, b) (a < b ? a : b)
#define ii pair<int, int>
#define fi first
#define se second
const int MAX = 200000; //2 * 10^5
const int MOD = 1000000007; //10^9 + 7
const int OO = 0x3f3f3f3f; // 0x3f3f3f3f;

int32_t main()
{
	int n, k;
	cin >> n >> k;
	vector<int> P, N, Z;

	for(int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		if(x > 0) P.push_back(x);
		else if(x < 0) N.push_back(x);
		else Z.push_back(x);
	}
	sort(P.begin(), P.end());
	sort(N.rbegin(), N.rend());
	
	vector<int> ans;

	while(k > 1 and (P.size() > 1 or N.size() > 1))
	{
		int a = 0, b = 0;
		if(P.size() > 1)
		{
			a = P.back();
			P.pop_back();
			b = P.back();
			P.pop_back();
		}

		int c = 0, d = 0;
		if(N.size() > 1)
		{
			c = N.back();
			N.pop_back();
			d = N.back();
			N.pop_back();
		}

		if(c * d >= a * b)
		{
			ans.push_back(c);
			ans.push_back(d);
			if(a and b)
			{
				P.push_back(b);
				P.push_back(a);
			}
		}
		else
		{
			ans.push_back(a);
			ans.push_back(b);
			if(c and d)
			{
				N.push_back(d);
				N.push_back(c);
			}
		}

		k -= 2;
	}
	while(k > 0 and P.size() > 0)
	{
		ans.push_back(P.back());
		P.pop_back();
		k--;
	}
	while(k > 0 and Z.size() > 0)
	{
		ans.push_back(Z.back());
		Z.pop_back();
		k--;
	}
	if(k > 0 and N.size() > 0)
	{
		sort(ans.begin(), ans.end());
		while(!ans.empty() and ans.back() < 0) 
		{
			N.push_back(ans.back());
			ans.pop_back();
			k++;
		}
		sort(N.rbegin(), N.rend());
		for(int i = 0; i < k; i++)
			ans.push_back(N[i]);
	}

	int res = 1;

	for(int &w : ans)
	{
		res = (res * w) % MOD;
		if(res < 0) res += MOD;
	}
	cout << res << '\n';

	return 0;
}


Measured memory_bytes: 7884
# -*- coding: utf-8 -*-

n = int(raw_input())
spot = [0] + map(int, raw_input().split()) + [0]

all_sum = 0
for j in range(n+1):
    all_sum = all_sum + abs(spot[j+1] - spot[j])

for i in range(n):
    ans = all_sum - abs(spot[i+1] - spot[i]) - abs(spot[i+2] - spot[i+1]) + abs(spot[i+2] - spot[i])
    print(ans)

Measured memory_bytes: 11132
#include <cstdio>
typedef long long ll;
inline char tc(){
  static char fl[100],*A=fl,*B=fl;
  return A==B&&(B=(A=fl)+fread(fl,1,100,stdin),A==B)?EOF:*A++;  
}
inline ll read(){
  ll a=0;static char c;
  while((c=tc())<48||c>57);
  while(c>=48&&c<=57)a=a*10+c-48,c=tc();
  return a;
}
inline ll gcd(ll a, ll b) {
  return b != 0 ? gcd(b, a % b) : a;
}
int main(){
    int n;
    ll ans=1,x;
    n=read();
    while(n--){
      x=read();
      ans=ans/gcd(ans,x)*x;
    }
    printf("%lld\n",ans);
    return 0;
}

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

int n, m, x, c[12], a[12][12];
int main() {
  cin >> n >> m >> x;
  rep(i,n) {
    cin >> c[i];
    rep(j,m) cin >> a[i][j];
  }
  
  int ans = mod;
  
  rep(bit,1<<n) {
    int cost = 0;
    vector<int> pts(m);
    rep(i,n) {
      if (bit >> i & 1) {
        cost += c[i];
        rep(j,m) pts[j] += a[i][j];
      }
    }
    bool judge = true;
    rep(j,m) if (pts[j] < x) judge = false;
    if (judge) ans = min(ans, cost);
  }
  
  if (ans == mod) cout << -1 << endl;
  else cout << ans << endl;
}

Measured memory_bytes: 3648
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        sc.close();
        long sum = 0;
        
        for(int i = 1; i <= N; i++) {
        	if(!(i%3 == 0 || i%5 ==0)) {
        		sum += i;
        	}
        }
        System.out.println(sum);



        
        }
	}



Measured memory_bytes: 35656
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define SORT(v) sort(v.begin(),v.end())
#define fori(i,a,b) for(ll i=a;i<b;i++)
#define M 1000000007
#define deb(x) cout<< #x << " " << x << endl;

double pi=3.14159265358979323846;

typedef pair<int,int> pii;
typedef pair<long long int, long long int>pll;
typedef vector<int>vi;
typedef vector<long long int>vl;
#define MAXN 10000001

int main ()
{
    ll T;
    T=1;
    //cin>>T;
    while(T--)
    {
   vi x(5);
   fori(i,0,5)cin>>x[i];
   SORT(x);
   bool b=false;
   fori(i,0,5){if(x[i]!=i){cout<<i<<endl;b=true;break;}}
        if(!b)cout<<5<<endl;
    }
    return 0;
}


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

const int N = 303;
const int MOD = 998244353;

int n, k;
char s[N];

vector<int> ones;

int dp[N][N][N];
int f(int x, int use, int sum) {
  if (use > k) return 0;
  if (x < 0) return sum == 0;
  if (~dp[x][use][sum]) return dp[x][use][sum];

  int ret = f(x-1, use, sum);
  for (int i = 1; i <= ones[x]; ++i) {
    ret = (ret + f(x-1, use + i, sum + i)) % MOD;
  }
  for (int i = 1; i <= sum; ++i) {
    ret = (ret + f(x-1, use, sum - i)) % MOD;
  }

  return dp[x][use][sum] = ret;
}

int solve() {
  scanf("%s %d", s, &k);
  
  int n = strlen(s);
  ones.push_back(0);
  for (int i = 0; i < n; ++i) {
    if (s[i] == '0') {
      ones.push_back(0);
    } else {
      ++ones.back();
    }
  }

  // for (int o: ones) cerr << o << " "; cerr << endl;

  memset(dp, -1, sizeof dp);
  printf("%d\n", f((int) ones.size() - 1, 0, 0));
  return 0;
}

int main() {
  int t = 1;
  // scanf("%d", &t);
  while (t--) solve();
  return 0;
}


Measured memory_bytes: 112496
#include<iostream>
#include<algorithm>
using namespace std;
int main(void)
{ 
  int i,j,k,a,b,ans;
  cin>>a>>b;
  i=0;
  while(1)
  {
    i++;
    if(i*8/100==a&&i*10/100==b){cout<<i;return 0;}
    if(i*8/100>a&&i*10/100>b){cout<<"-1";return 0;}
  }
  return 0;
}

Measured memory_bytes: 3580
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
typedef pair<int,int> P;

#define INF 1000000
int cost[10][10];
int n,m;

int main(){
  while(1){
    cin >> n;
    if(!n)break;

    m = 0;
    for(int i=0;i<10;i++){
      for(int j=0;j<10;j++){
        if(i==j){
          cost[i][j] = 0;
        }else{
          cost[i][j] = INF;
        }
      }
    }
    for(int i=0;i<n;i++){
      int x,y,z;
      scanf("%d%d%d",&x,&y,&z);
      if(m<x||m<y){
        m = max(x,y);
      }
      cost[x][y] = z;
      cost[y][x] = z;
    }
    m++;

    for(int k=0;k<m;k++){
      for(int i=0;i<m;i++){
        for(int j=0;j<m;j++){
          cost[i][j] = min(cost[i][j],cost[i][k]+cost[k][j]);
        }
      }
    }

    /*for(int i=0;i<m;i++){
      for(int j=0;j<m;j++){
        printf("%d%c",cost[i][j],j==m-1?'\n':' ');
      }
    }*/

    int mini = INF;
    int index;
    for(int i=0;i<m;i++){
      int sum = 0;
      for(int j=0;j<m;j++){
        sum += cost[i][j];
      }
      if(mini>sum){
        mini = sum;
        index = i;
      }
    }
    cout << index << " " << mini << endl;
  }
}

Measured memory_bytes: 1244
#include<iostream>
#include<vector>
using namespace std; 
long long int abso(long long int x)
{
  if(x>0)
  {
     return x;
  }
  else
  {
    return -x;
  }
}
int main()
{
	int n;
    cin>>n;
    vector<long long int> v(n);
    for(int i=0;i<n;i++)
    {
    	cin>>v[i];
    }
    vector<long long int> dp(n);
    dp[0]=0;
    for(int i=1;i<n;i++)
    {
        if(i>1)
        {
        	dp[i]=min(dp[i-1]+abso(v[i]-v[i-1]),dp[i-2]+abso(v[i]-v[i-2]));
        }
        else
        {
        	dp[i]=dp[i-1]+abso(v[i]-v[i-1]);
        }
	}
    cout<<dp[n-1];
 
}

Measured memory_bytes: 1792
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val l = readLine()!!.split(' ').map { it.toInt() }
    var sum = 0
    for (i in 0 until n) {
        val a = readLine()!!.toDouble()
        sum += Math.floor((l[0]-1)/a).toInt() + 1
    }
    println(sum+l[1])
}


Measured memory_bytes: 36384
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
	ll ans=0;

	ll x,k,d;
	cin >> x >> k >> d;

	//xがd*k
	x=abs(x);
	if(double(x/d) > k)//d*kでかい
	{
		ans = x - d*k;
	}else{//xは正と負の場合
		int tmp = k-x/d;
		if(tmp%2==0)//偶数
		{
			ans=x%d;
		}else{//奇数
			ans=x%d - d;
		}

	}//xは負の場合

	cout << abs(ans) << endl;

}


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

bool finish(int a, int b) {
    return (a <= 3 && b == 5 || b <= 3 && a == 5 || a == 5 && b == 5 || a == 6 && b == 4 || b == 6 && a == 4);
}

void dfs(string res, int a, int b, int j, int y) {
    if(a == j && b == y) {
        cout << res << endl;
        return;
    }
    if(finish(a, b)) {
        return;
    }
    dfs(res+'A', a+1, b, j, y);
    dfs(res+'B', a, b+1, j, y);
}

int main() {
    int j, y;
    cin >> j >> y;
    dfs("", 0, 0, j, y);
}


Measured memory_bytes: 3224
package main

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

var sc = NewScanner(os.Stdin, 1000000)

func main() {
	var K int
	list := map[int]int{}
	N := sc.readInt()
	M := sc.readInt()
	for i := 0; i < M; i++ {
		list[i+1] = 0
	}
	for i := 0; i < N; i++ {
		K = sc.readInt()
		for j := 0; j < K; j++ {
			a := sc.readInt()
			list[a]++
		}
	}
	var res int
	for i := 0; i < M; i++ {
		if list[i+1] == N {
			res++
		}
	}
	fmt.Println(res)

}

type Scanner struct {
	*bufio.Scanner
}

func (scn *Scanner) readInt() int {
	scn.Scanner.Scan()
	i, _ := strconv.Atoi(scn.Scanner.Text())
	return i
}

func NewScanner(r io.Reader, bufSize int) *Scanner {
	buf := make([]byte, bufSize)
	scn := bufio.NewScanner(r)
	scn.Buffer(buf, bufSize)
	scn.Split(bufio.ScanWords)
	return &Scanner{scn}
}


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

typedef long long ll;
int N, A, B;
vector<ll> H;

bool f(ll x) {
    ll cnt = 0;
    for(int i = 0; i < N; i++) {
        cnt += (max(0LL, H[i] - x*B) + (A - B - 1)) / (A - B);
    }
    return cnt <= x;
}

int main() {
    scanf("%d %d %d", &N, &A, &B);
    H.resize(N);
    for(int i = 0; i < N; i++) {
        scanf("%lld", &H[i]);
    }
    ll s = 0, e = 1e9;
    ll ans;
    while(s <= e) {
        ll m = (s + e)>>1;
        if(f(m)) {
            ans = m;
            e = m - 1;
        }
        else s = m + 1;
    }
    printf("%lld", ans);
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T,class U> using P = pair<T,U>;
template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vec<T>>;

constexpr ll mod = 1e9+7;
struct mint {
    ll x;
    mint(ll x=0):x((x%mod+mod)%mod){}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const {
        mint res(*this);
        return res/=a;
    }
};

mint dp[310][310][310] = {};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,M;
    cin >> N >> M;
    dp[0][1][0] = 1;
    for(int i=0;i<M;i++) for(ll j=0;j<=N;j++) for(ll k=0;k<=N;k++){
        //新しい頂点に行く
        if(j+k<N) dp[i+1][j][k+1] += dp[i][j][k]*(N-j-k);
        //まだ強連結じゃない頂点に戻る
        dp[i+1][j][k] += dp[i][j][k]*k;
        //強連結にする
        if(j+k<=N) dp[i+1][j+k][0] += dp[i][j][k]*j;
    }
    cout << dp[M][N][0].x << endl;
}

Measured memory_bytes: 232960
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(c) (c).begin(),(c).end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define TRACE
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

const ll inf = 2e18;
const int mod = 1e9 + 7;
const int N = 2e4 + 10;

int dp[N];

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

	int n;
	cin >> n;
	int w[n + 1], s[n + 1], v[n + 1];
	vi ord;
	for(int i = 1; i <= n; i++) {
		cin >> w[i] >> s[i] >> v[i];
		ord.pb(i);
	}
	sort(all(ord), [&](const int a, const int b) {return (s[a] + w[a]) < (s[b] + w[b]);});
	memset(dp, -1, sizeof(dp));
	dp[0] = 0;
	for(int i : ord) {
		for(int j = s[i]; j >= 0; j--) {
			if(j + w[i] < N && dp[j] != -1) {
				dp[j + w[i]] = max(dp[j + w[i]], dp[j] + v[i]);
			}
		}
	}
	cout << *max_element(dp, dp + N);

	return 0;
}

Measured memory_bytes: 3844
#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
int main() {
  int N, M;
  cin >> N >> M;
  vector<int> A(N);
  int sum = 0;
  
  for (int i=0; i<N; i++){
    cin >> A.at(i);
    sum += A.at(i);
  }
  int ans = 0;
  for (int i=0; i<N; i++){
    if(sum <= A.at(i)*4*M){
      ans++;
    }
  }
  if( ans >= M){
    cout << "Yes" <<endl;
  }
  else{
    cout <<"No" << endl;
  }
}
  

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file  
#include <ext/pb_ds/tree_policy.hpp>  
#include <functional> // for less  
using namespace         std;
#define                 int long long
#define                 double long double
#define                 pb push_back
#define                 mp make_pair
#define st(arr,a)       memset(arr,a,sizeof arr)
#define                 nl cout<<endl
#define                 endl '\n'              
#define bitcount(x)     __builtin_popcountll(x)
const int MOD = 1000000007ll;
#define forn(i,a,b)     for(int i=a;i<=b;i++)
#define rfor(i,a,b)     for(int i=a;i>=b;i--)
#define all(x)          x.begin() , x.end()
#define pi pair<int,int>
#define X first
#define Y second
#define N 1014159
#define  vi vector<int>
#define  v  vector
#define die exit(0)
using namespace __gnu_pbds;  
typedef tree<int, null_type, less<int>, rb_tree_tag,  
            tree_order_statistics_node_update> oset; 
gp_hash_table<int, int> table;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
    int operator()(int x) const { return x ^ RANDOM; }
};

int n;
int arr[N];

void solve()
{
    int m;
    cin>>n>>m;
    forn(i,1,n)
    {
        cin>>arr[i];
    }
    int a = -1,b;
    forn(i,2,n)
    {
        if(arr[i] + arr[i-1]>=m)
        {
            a = i-1 , b = i;
            break;
        }
    }
    if(a==-1)
    {
        cout<<"Impossible";exit(0);
    }

    cout<<"Possible\n";
    forn(i,1,a-1)
    {
        cout<<i<<"\n";
    }
    rfor(i,n-1,b)
    {
        cout<<i<<"\n";
    }
    cout<<a;


    
}


signed main() 
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
    int t = 1;
    //cin>>t;
    forn(i,1,t)
    {
        solve();
        nl;
    }



    return 0;

}

//       g++ -g c.cpp ; timeout 2s ./a.out

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

int main(){
  int N;
  cin >> N;
  
  int max_H = 0, ans = 0;
  for(int i = 0;i < N;i++){
    int H;
    cin >> H;
    
    if(max_H <= H){
      max_H = H;
      ans++;
    }
  }
  
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 3624
result = input().split()
message = "NO"
if int(result[0]) == 7:
    if int(result[1]) == 5:
        if int(result[2]) == 5:
            message = "YES"
elif int(result[0]) == 5:
    if int(result[1]) == 7:
        if int(result[2]) == 5:
            message = "YES"
    elif int(result[1]) == 5:
        if int(result[2]) == 7:
            message = "YES"
print(message)

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

dy = [1,0,-1,0,1,-1,1,-1]
dx = [0,1,0,-1,1,1,-1,-1]


for y in range(h):
    for x in range(w):
        if s[y][x] == '#':
            continue
        
        cnt = 0
        for k in range(8):
            ny = y + dy[k]
            nx = x + dx[k]
            
            if ny < 0 or h <= ny or nx < 0 or w <= nx:
                continue
            
            if s[ny][nx] == "#":
                cnt += 1
                
        s[y][x] = str(cnt)
for y in range(h):
    print(''.join(s[y]))

Measured memory_bytes: 3188