akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define rep(i,n) for (int i=0; i<n; i++)
#define REP(i,x,n) for (int i=x; i<n; i++)
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;

int main(){
  int n;
  ll k;
  cin >> n >> k;
  vector<pair<int,int>> vec;
  rep(i,n){
    int a, b;
    cin >> a >> b;
    vec.push_back(make_pair(a,b));
  }
  sort(vec.begin(),vec.end());

  ll cnt = 0;
  for (pair<int,int> p: vec){
    int a, b;
    tie(a,b) = p;
    cnt += b;
    if (cnt >= k){
      cout << a << endl;
      return 0;
    }
  }
}


Measured memory_bytes: 4288
*li, = map(int, open(0).read().split())
new = []
mini = 10
for i in range(len(li)):
    if li[i] % 10 == 0:
        new.append(li[i])
    else:
        new.append(li[i] // 10 * 10 + 10)
        if mini > li[i] % 10:
            mini = li[i] % 10
# print(new)
print(sum(new)-(10-mini))


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

class UnionFind{
    vector<int>p,r;
public:
    UnionFind(int n){
        p.resize(n,-1);
        r.resize(n,1);
    }
    int find(int x){
        if(p[x] == -1)return x;
        else return p[x] = find(p[x]);
    }
    void unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y)return;
        if(r[x] > r[y])swap(x,y);
        if(r[x] == r[y])r[y]++;
        p[x] = y;
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
};

int main(){
    int n,q;
    cin>>n>>q;
    UnionFind uf(n);
    rep(i,q){
        int com,x,y;
        cin>>com>>x>>y;
        if(com==0){
            uf.unite(x,y);
        }
        else{
            cout<<(uf.same(x,y)?1:0)<<endl;
        }
    }
}


Measured memory_bytes: 3196
#include <bits/stdc++.h>
using namespace std;
#define MD 1000000007
typedef long long int ll;
typedef pair<ll, ll> P;
template <typename T>
std::string tostr(const T &t){std::ostringstream os;os << t;return os.str();}
int dx[4]={1, 0, -1, 0}, dy[4]={0, 1, 0, -1};

int main()
{
   int n;
   cin>>n;
   string s,a;
   cin>>s;
   a=s;
   int len=s.length();
   for(int i=0;i<len;i++){
       a[i]='#';
   }
    int ans=0,tmp=0;
    for(int i=0;i<len;i++){
        if(s[i]!=a[i]){
            tmp++;
        }
    }
    ans=tmp;
    for(int i=0;i<len;i++){
        if(s[i]=='.'){
            tmp--;
        }else{
            tmp++;
        }
        ans=min(ans,tmp);
    }
    cout<<ans<<endl;
    return 0;
}

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


string S;

void Main() {
  cin >> S;

  int ans = 0;
  for (int i = 0; i < int(S.size()) - 1 - i; ++i) {
    if (S[i] != S[int(S.size()) - 1 - i]) ans++;
  }

  cout << ans << endl;
}

int main() {
  Main();
  return 0;
}

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

int main(){
	int h, k[MAX];
	
	cin>>h;
	
	for(int i = 1; i <= h; i++)
		cin>>k[i];
	
	for(int i = 1; i <= h; i++)
		cout<<"node "<<i<<": key = "<<k[i]<<(i==1?"":", parent key = ")<<(i==1?"":to_string(k[i/2]))<<","<<(2*i<=h?" left key = ":"")<<(2*i<=h?to_string(k[2*i]):"")<<(2*i<=h?",":"")<<(2*i+1<=h?" right key = ":"")<<(2*i+1<=h?to_string(k[2*i+1]):"")<<(2*i+1<=h?",":"")<<" "<<endl;
	
	return 0;
}


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

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1010;

int n, m;
char a[N][N], b[N][N];

bool check(int r, int c)
{
    for(int i = 1; i <= m; i++)
        for(int  j = 1; j <= m; j++)
            if(a[i + r - 1][j + c - 1] != b[i][j])
                return false;
    return true;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%s", a[i] + 1);
    for(int i = 1; i <= m; i++) scanf("%s", b[i] + 1);

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(check(i, j))
            {
                puts("Yes");
                return 0;
            }

    puts("No");

    return 0;
}


Measured memory_bytes: 384
#include<stdio.h>

int attack(int hp, int at) {
    hp -= at;
    return hp;
}

int main() {
    int taka_hp, taka_at;
    int aoki_hp, aoki_at;
    scanf("%d %d %d %d", &taka_hp, &taka_at, &aoki_hp, &aoki_at);
    while(1) {
        aoki_hp = attack(aoki_hp, taka_at);
        if(aoki_hp <= 0) {
            printf("Yes\n");
            break;
        }
        taka_hp = attack(taka_hp, aoki_at);
        if(taka_hp <= 0) {
            printf("No\n");
            break;
        }
    }
}


Measured memory_bytes: 1664
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>


using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

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

#define pb push_back
#define mp make_pair
#define mt make_tuple

// 負の数にも対応した mod
// 例えば -17 を 5 で割った余りは本当は 3 (-17 ≡ 3 (mod. 5))
// しかし単に -17 % 5 では -2 になってしまう
inline ll mod(ll a, ll m) {
    return (a % m + m) % m;
}

// 拡張 Euclid の互除法
// ap + bq = gcd(a, b) となる (p, q) を求め、d = gcd(a, b) をリターンします
ll extGcd(ll a, ll b, ll &p, ll &q) {  
    if (b == 0) { p = 1; q = 0; return a; }  
    ll d = extGcd(b, a%b, q, p);  
    q -= a/b * p;  
    return d;  
}

// 中国剰余定理
// リターン値を (r, m) とすると解は x ≡ r (mod. m)
// 解なしの場合は (0, -1) をリターン
// e.g. 3で割って2余り、5で割って3余る数を求めたいとき
//      すなわち x ≡ 2 (mod. 3) かつ x ≡ 3 (mod. 5) である xを求めたいとき
//      ChineseRem(2, 3, 3, 5) で (8, 15) が戻る。
//      これは、解が x ≡ 8 (mod. 15) であることを意味する
pair<ll, ll> chineseRemSimple(ll b1, ll m1, ll b2, ll m2) {
    ll p, q;
    ll d = extGcd(m1, m2, p, q); // p is inv of m1/d (mod. m2/d)
    if ((b2 - b1) % d != 0) return make_pair(0, -1);
    ll m = m1 * (m2/d); // lcm of (m1, m2)
    ll tmp = (b2 - b1) / d * p % (m2/d);
    ll r = mod(b1 + m1 * tmp, m);
    return make_pair(r, m);
}

// 中国剰余定理
// リターン値を (r, m) とすると解は x ≡ r (mod. m)
// 解なしの場合は (0, -1) をリターン
pair<ll, ll> chineseRem(const vector<ll> &b, const vector<ll> &m) {
    ll r = 0, M = 1;
    for (int i = 0; i < (int)b.size(); ++i) {
        ll p, q;
        ll d = extGcd(M, m[i], p, q); // p is inv of M/d (mod. m[i]/d)
        if ((b[i] - r) % d != 0) return make_pair(0, -1);
        ll tmp = (b[i] - r) / d * p % (m[i]/d);
        r += M * tmp;
        M *= m[i]/d;
    }
    return make_pair(mod(r, M), M);
}

int main(void)
{
    cin.sync_with_stdio(false);
    ll N, M;
    cin >> N >> M;

    vector<ll> Bs;
    vector<ll> Ms;
    REP(n, N) {
        ll a;
        cin >> a;
        // Xは、aで割るとあまりがa/2であるような数
        Ms.pb(a);
        Bs.pb(a / 2);
    }

    // 中国剰余定理でXの条件を求めると、
    // X ≡ r (mod. m) と分かる
    auto ret = chineseRem(Bs, Ms);
    auto r = ret.first;
    auto m = ret.second;
    cerr << "r, m = " << r << ", " << m << endl;

    if (r == 0 && m == -1) {
        cout << 0 << endl;
    }
    else {
        ll ans = M / m;
        // 端数分を考慮
        if (M % m != 0 && (M - (M / m) * m) >= r) ++ans;
        cout << ans << endl;
    }

    return 0;
}


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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);

	ll x; cin >> x;
	for (ll a = -1000; a <= 1000; a++)
		for (ll b = -1000; b <= 1000; b++) {
			if (a*a*a*a*a - b*b*b*b*b == x) {
				cout << a << " " << b << endl;
				return 0;
			}
		}
}


Measured memory_bytes: 3648
using System;
using System.Collections.Generic;
using System.Linq;
using BitArray = System.Collections.BitArray;
using BigInteger = System.Numerics.BigInteger;
using TextReader = System.IO.TextReader;

namespace AtCoderProject
{
    public class Program
    {
        public object Calc()
        {
            var N = consoleReader.Int;
            return consoleReader.Split.Int.Sum(i => Div2(i));
        }

        static int Div2(int n)
        {
            int count = 0;
            int remainder;
            while (true)
            {
                n = Math.DivRem(n, 2, out remainder);
                if (remainder != 0) break;
                count++;
            }
            return count;
        }

        #region いつもの
        private readonly ConsoleReader consoleReader;
        public Program(ConsoleReader consoleReader) { this.consoleReader = consoleReader; }
        static void Main() => Console.WriteLine(new Program(new ConsoleReader(Console.In)).Calc()); static string AllLines<T>(IEnumerable<T> source) => string.Join("\n", source);
        #endregion
    }

#pragma warning disable
    public class ConsoleReader
    {
        private string[] line = Array.Empty<string>();
        private int linePosition;
        private TextReader textReader;
        public ConsoleReader(TextReader tr) { textReader = tr; }
        public int Int => int.Parse(String);
        public long Long => long.Parse(String);
        public double Double => double.Parse(String);
        public string String
        {
            get
            {
                if (linePosition >= line.Length)
                {
                    linePosition = 0;
                    line = textReader.ReadLine().Split();
                }
                return line[linePosition++];
            }
        }
        public class SplitLine
        {
            private string[] splited;
            public SplitLine(ConsoleReader cr) { splited = cr.textReader.ReadLine().Split(); }
            public int[] Int => String.Select(x => int.Parse(x)).ToArray();
            public long[] Long => String.Select(x => long.Parse(x)).ToArray();
            public double[] Double => String.Select(x => double.Parse(x)).ToArray();
            public string[] String => splited;
        }
        public SplitLine Split => new SplitLine(this);
        public class RepeatReader
        {
            ConsoleReader cr; int count;
            public RepeatReader(ConsoleReader cr, int count) { this.cr = cr; this.count = count; }
            public IEnumerable<T> Select<T>(Func<ConsoleReader, T> func) { for (int i = 0; i < count; i++) yield return func(cr); }
            public IEnumerable<string> String { get { for (int i = 0; i < count; i++) yield return cr.String; } }
            public IEnumerable<int> Int { get { for (int i = 0; i < count; i++) yield return cr.Int; } }
            public IEnumerable<double> Double { get { for (int i = 0; i < count; i++) yield return cr.Double; } }
        }
        public RepeatReader Repeat(int count) => new RepeatReader(this, count);
    }
}

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

using namespace std;

int main()
{
//    freopen("in.txt","r",stdin);

    int a[110][110];
    int b[110];
    int c[110];
    int n,m;
    while(scanf("%d %d",&n,&m)==2)
    {
        memset(c,0,sizeof(c));
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                scanf("%d",&a[i][j]);

            }
        }
        for(int i=0;i<m;i++)
        {
            scanf("%d",&b[i]);
        }

        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                c[i]+=a[i][j]*b[j];
            }
            printf("%d\n",c[i]);
        }
    }
}



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

typedef long long int ll;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<string> vs;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define REPR(i,n) for(int i=n-1;i>=0;i--)
#define FORR(i,n,m) for(int i=n-1;i>=m;i--)
#define ARR(array) for(int i=0;i<array.size();i++)
#define all(in) (in).begin(),(in).end()
#define ALL(in,K) (in),(in)+(K)

#define INF 1e18
#define MOD 1000000007
#define SIZE 10005
#define PI 	3.14159265358979323846

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; } //最大公約数
ll lcm(ll a, ll b) { return a/gcd(a, b)*b; } //最小公倍数

ll input(){
  ll a;
  cin >> a;
  return a;
}

int main(){
  int n,a,b;
  cin >> n >> a >> b;
  int ans = 0;
  REP(i,n+1){
    int c = i;
    int wa=0;
    while(c){
      wa+=c%10;
      c/=10;
    }
    if(a<=wa && wa<=b){
      //cout << wa << endl;
      ans+=i;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;

int main(){
    int h,a;
    cin >> h >> a;
    if(h%a==0){
        cout << h/a << endl;
    }else{
        cout << (h/a)+1 << endl;
    }
}

Measured memory_bytes: 256
import java.util.*;
 
public class Main {
	public static void main (String[] args) {
		Scanner in = new Scanner(System.in);
		
		int a = in.nextInt();
        double nam = 0;
      
      for(int i = 0;i < a ;i++){
      nam += 1.0/in.nextDouble();
      }
      System.out.print(1.0/nam);
	}
}

Measured memory_bytes: 23252
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))

def main():
    N = INT()
    A = LI()
    RGB = [0,0,0]
    answer = 1
    MOD = 10**9+7

    for i in range(N):
        if RGB.count(A[i]) == 0:
            print(0)
            return

        answer *= RGB.count(A[i])
        answer %= MOD
        for j in range(3):
            if RGB[j] == A[i]:
                RGB[j] += 1
                break

    print(answer)
    return

if __name__ == '__main__':
    main()


Measured memory_bytes: 14376
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define pb push_back
#define fr(i,n) for(int i=0;i<n;i++)
#define Fr(i,n) for(int i=0;i++<n;)
#define ifr(i,n) for(int i=n-1;i>=0;i--)
#define iFr(i,n) for(int i=n;i>0;i--)

int main(){
  ll n,a[100010],c=0,d,e;
  cin>>n;
  fr(i,n) cin>>a[i];
  sort(a,a+n);
  reverse(a,a+n);
  fr(i,n-1){
    if(c==2) break;
    if(c==0&&a[i]==a[i+1]&&a[i+1]==a[i+2]&&a[i+2]==a[i+3]){
      d=a[i];e=a[i];c=2;
    }
    if(a[i]==a[i+1]&&a[i]!=d){
      if(c==0) d=a[i];
      if(c==1) e=a[i];
      c++;
    }
  }
  cout<<((c==2)?d*e:0)<<endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;

int main()
{
	int N;
	cin >> N;
	map<P, int> cnt;
	for (int i = 0; i < N; i++) {
		int x, y, w;
		cin >> x >> y >> w;
		for (int j = 0; j < 2; j++) {
			for (int k = 0; k < 2; k++) {
				cnt[P(x + j, y + k)] += w;
			}
		}
	}
	int res = 0;
	for (auto p : cnt) {
		res = max(res, p.second);
	}
	cout << res << " / " << 1 << endl;
	return 0;
}

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

int main() {
	int A,B,H,M;
  	cin>> A >> B >> H >> M;
  	
  	double x=sqrt(A*A+B*B-2*A*B*cos(M_PI/180*(5.5*M-30*H)));
  
  	cout<< fixed << setprecision(15) << x <<endl;
}

Measured memory_bytes: 4228
#include <bits/stdc++.h>
#define INF 1e9
#define EPS 1e-9
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define arr array
#define _min(a) *min_element(a.begin(), a.end());
#define _max(a) *max_element(a.begin(), a.end());
#define _sort(x) sort(x.begin(), x.end())
#define _rsort(x) sort(x.rbegin(), x.rend())
#define _reverse(x) reverse(x.begin(), x.end())
#define _debug(x) cout << #x << " = " << x << endl;
#define debug(x, y) cout << #x " = " << x << " " << #y << " = " << y << endl;
#define _lower_bound(a, x) lower_bound(a.begin(), a.end(), x) - a.begin()
#define _upper_bound(a, x) upper_bound(a.begin(), a.end(), x) - a.begin()
typedef long long ll;
using namespace std;

void solve() {	 
	int n, cnt = 0; cin >> n;
	vector<int> a(n); for (auto &u : a) cin >> u;
	for (int i = 1; i < n - 1; ++i) {
		if (a[i] > a[i - 1] && a[i] < a[i + 1] || a[i] < a[i - 1] && a[i] > a[i + 1]) {
			++cnt;
		}
	}
	cout << cnt << endl;
}

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

    // int t; cin >> t;
    // while(t--) 
        solve();
}

Measured memory_bytes: 3624
#include<stdio.h>
int main(void)
{
	int n,p[1000],x,i;
	double h[1000],w[1000],y;
	scanf("%d",&n);
	while(n!=0){
		for(i=0;i<n;i++) {
			scanf("%d %lf %lf",&p[i],&h[i],&w[i]);
			h[i]=h[i]/100;
			h[i]=w[i]/(h[i]*h[i]);
		
//			if(h[i]<0)  h[i]=h[i]*-1;
			
			h[i]=h[i]-22;
			if(h[i]<0)  h[i]=h[i]*-1;
//			printf("p=%d h=%d\n",p[i],h[i]);
		}
		x=p[0]; y=h[0];
		for(i=1;i<n;i++){
			if(y>h[i]){
				x=p[i];  y=h[i];
			}
		}
		printf("%d\n",x);
		scanf("%d",&n);
	}
	return 0;
}

Measured memory_bytes: 2716
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int mod = 1000000007;
string a, b, c;
int main() {
	while (cin >> a >> b >> c) {
		reverse(a.begin(), a.end());
		reverse(b.begin(), b.end());
		reverse(c.begin(), c.end());
		int n = a.size();
		vector<vector<int> > dp(n + 1, vector<int>(20, 0)); dp[0][0] = 1;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= 9; j++) {
				if (i + 1 == n && j == 0) continue;
				if (a[i] != '?' && a[i] != j + 48) continue;
				for (int k = 0; k <= 9; k++) {
					if (i + 1 == n && k == 0) continue;
					if (b[i] != '?' && b[i] != k + 48) continue;
					for (int l = 0; l <= 19; l++) {
						int w = j + k + l / 10;
						if (c[i] != '?' && c[i] != w % 10 + 48) continue;
						dp[i + 1][w] += dp[i][l];
						dp[i + 1][w] %= mod;
					}
				}
			}
		}
		int ret = 0;
		for (int i = 1; i <= 9; i++) ret += dp[n][i], ret %= mod;
		cout << ret << endl;
	}
	return 0;
}

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

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

LL digit(LL x, LL d) {
    if(x == 0)
        return 1;
    LL res = 0;
    for(;0 < x;) {
        x /= d;
        res++;
    }
    return res;
}

LL s(LL x) {
    LL res = 0;
    for(;x != 0;x /= 10) {
        res += x%10;
    }
    return res;
}

int main() {
    LL K;
    cin >> K;

    FOR(i, 1, min<LL>(10, K + 1)) {
        cout << i << endl;
    }
    K -= min<LL>(9, K);

    LL N = 10;
    for(LL i = 0;i < K;) {
        double t = 1e18;
        LL d = digit(N, 10);
        LL res = N;
        REP(j, d) {
            LL x = N;
            LL p = pow(10, j + 1);
            x /= p;
            x += 1;
            x *= p;
            x -= 1;
            if((double)x/s(x) < t) {
                res = x;
                t = (double)x/s(x);
            }
        }
            cout << res << endl;
            N = res + 1;
            i++;
    }
    return 0;
}



Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define sd(x) scanf("%d", &x)
#define sz(v) (int) v.size()
#define pr(v) For(i, 0, sz(v)) {cout<<v[i]<<" ";} cout<<endl;
#define slld(x) scanf("%lld", &x)
#define all(x) x.begin(), x.end()
#define For(i, st, en) for(ll i=st; i<en; i++)
#define tr(x) for(auto it=x.begin(); it!=x.end(); it++)
#define fast std::ios::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define ll long long
#define int long long
#define mp make_pair
#define F first
#define S second
typedef pair<int, int> pii;
typedef vector<int> vi;
#define MOD 1000000007
#define INF 1000000000000000007LL

const int N = 300005;
 
// it's swapnil07 ;)
 
#ifdef SWAPNIL07
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
int begtime = clock();
#define end_routine() cout << "\n\nTime elapsed: " << (clock() - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n";
#else
#define endl '\n'
#define trace(...)
#define end_routine()
#endif

int a[N], ans[N];
vector<int> adj[N];

vector<int> vect;

void dfs(int u, int p){
    bool fl = false;
    int val;
    int pos = lower_bound(all(vect), a[u])-vect.begin();
    if(pos!=sz(vect)){
        fl = true;
        val = vect[pos];
        vect[pos]=a[u];
    }
    else{
        vect.pb(a[u]);
    }
    ans[u]=sz(vect);

    for(int v: adj[u]){
        if(v!=p){
            dfs(v, u);
        }
    }
    if(!fl){
        vect.pop_back();
    }
    else{
        vect[pos]=val;
    }
}


void solve(){
    int n; cin>>n;
    For(i, 1, n+1){
        cin>>a[i];
    }
    For(i, 0, n-1){
        int u, v; cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    dfs(1, 0);
    For(i, 1, n+1){
        cout<<ans[i]<<"\n";
    }
}


signed main()
{
    fast
    #ifdef SWAPNIL07
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    int t=1;
    while(t--){
        solve();
    }
    return 0;
}





Measured memory_bytes: 34336
#include<iostream>
#include<cassert>
#include<algorithm>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<29)
#define MAX 3000000
using namespace std;
typedef long long ll;
struct P
{
  ll color,w;
  P(ll color=-inf,ll w=-inf):color(color),w(w){}
};
P par[MAX];
void init(){ rep(i,MAX)par[i] = P(i); }

P find(int x)
{
  if(x == par[x].color)return par[x];
  P p = find(par[x].color);
  if(par[x].w == -inf)par[x].w = 0;
  par[x].w += p.w,par[x].color = p.color;
  return par[x];
}

void unit(int x,int y,ll w)//x <= y
{
  P X = find(x); 
  P Y = find(y);
  //if(X.color == Y.color)return;
  par[X.color].color = par[Y.color].color;
  if(par[X.color].w == -inf)par[X.color].w = 0;
  if(par[Y.color].w == -inf)par[Y.color].w = 0;
  par[X.color].w = par[X.color].w + (par[y].w-w - par[x].w);
  //par[x].w -= par[y].w;
}

int N,M;

int main()
{
  while(cin >> N >> M,N|M)
    {
      init();
      char c;
      ll a,b,w;
      rep(_,M)
	{
	  cin >> c;
	  if(c == '!')
	    {
	      cin >> a >> b >> w;
	      unit(a,b,w);
	    }
	  else
	    {
	      cin >> a >> b;
	      P B = find(b);
	      P A = find(a);
	      if(B.w == -inf || A.w == -inf)cout << "UNKNOWN" << endl;
	      else if(B.color != A.color)cout << "UNKNOWN" << endl;
	      else cout << B.w-A.w << endl;
	    }

	  rep(i,10)
	    {
	      // cout << i << " = " << par[i].color << "," << par[i].w << endl;
	    }	
	  //cout << endl;

	}
    }
  return 0;
} 

Measured memory_bytes: 53252
#include <bits/stdc++.h>
using namespace std;
void Main();

using i8  = int8_t;   /* -128 ~ 127 */
using u8  = uint8_t;  /* 0 ~ 255 */
using i16 = int16_t;  /* -32,768 ~ 32,767 */
using u16 = uint16_t; /* 0 ~ 65,535 */
using i32 = int32_t;  /* -2,147,483,648 ~ 2,147,483,647 */
using u32 = uint32_t; /* 0 ~ 4,294,967,295 */
using i64 = int64_t;  /* -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 */
using u64 = uint64_t; /* 0 ~ 18,446,744,073,709,551,615 */
using f32 = float;    /* (-3.4 * 10^38) ~ (3.4 * 10^38) */
using f64 = double;   /* (-1.7 * 10^308) ~ (1.7 * 10^308) */
using f80 = __float80;
template <class T> using Vec = vector<T>;
constexpr i64 INF = 1010000000000000017;
constexpr i64 MOD = 1e9 + 7;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;
#define ALL(v) v.begin(), v.end()
#define GCD(a, b) __gcd(a, b) /* 最大公約数 */
#define LCM(a, b) a / __gcd(a, b) * b /* 最小公倍数 */

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

void Main() {
    for (u32 i = 1; i <= 5; i++) {
        u32 x;
        cin >> x;
        if (x == 0) {
            cout << i << endl;
            return;
        }
    }
}


Measured memory_bytes: 3648
#include <stdio.h>

int A[45];

int fib(int n){
  if(n == 0 || n == 1) return A[n] = 1;
  if(A[n] != -1) return A[n];
  return A[n] = fib(n-2)+fib(n-1);
}

int main(){
  int n,i;
  for(i=0;i<45;i++) A[i] = -1;
  scanf("%d",&n);
  printf("%d\n",fib(n));

  return 0;
}



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

int main() {
  char b;
  cin >> b;
  if (b == 'A') {
    cout << 'T' << endl;
  }
  else if (b == 'T') {
    cout << 'A' << endl;
  }
  else if (b == 'C') {
    cout << 'G' << endl;
  }
  else if (b == 'G') {
    cout << 'C' << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
	int H,W;
	while(1){
	cin>>H>>W;
	if(H==0&&W==0){
			break;
	}
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			cout<<"#";
		}
	    cout<<endl;
	}
	cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <string>
#include <vector>
typedef long long int ll;
using namespace std;

ll a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z;

long double T,X;
int main()
{
  cin>>T>>X;
  cout<<T/X<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <bitset>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
using ll = long long int;
const ll MOD = 1e9 + 7;

vector<string> dfs(string s, ll depth, vector<char> symbol)
{
    vector<string> ret;
    if (depth == 0)
    {
        ret.push_back(s);
        return ret;
    }

    for (ll i = 0; i < symbol.size(); i++)
    {
        auto vec = dfs(s + symbol[i], depth - 1, symbol);
        for (auto &&e : vec)
        {
            ret.push_back(e);
        }
    }
    return ret;
}

int main()
{
    ll X, A;
  cin >> X >> A;

    if (X < A) {
        cout << 0 << endl;
    } else {
        cout << 10 << endl;
    }
}

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

vector<vector<pair<int, int>>> v;
int ans = 0;

int mass[20];
int N;

int check(){
    bool f = true;
    vector<int> now(N, -1);
    int cnt = 0;
    for(int i = 0;i < N;i++){
      //  cout<<mass[i];
        if(mass[i] == 1){
            cnt++;
            for(auto a : v[i]){
                if(mass[a.first] != a.second)f = false; 
                if(now[a.first] == -1){
                    now[a.first] = a.second;
                }
                if(now[a.first] != a.second && now[a.first] != -1){
                    f = false;
                }
            }
        }
    }
    if(f){
        return cnt;
    }else{
        return 0;
    }
}

void dfs(int i){
    if(i == N){
        int s = check();
        ans = max(s, ans);
       // cout<<" "<<s<<endl;
        return;
    }
    mass[i] = 0;dfs(i + 1);
    mass[i] = 1;dfs(i + 1);
}


int main(){
    cin >> N;
    for(int i = 0;i < N;i++){
        int A;cin >> A;
        vector<pair<int, int>> m;
        for(int j = 0;j < A;j++){
            int x,y;cin >> x >> y;
            m.push_back({x-1, y});
        }
        v.push_back(m);
    }
    dfs(0);
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
module Main where
import Control.Applicative ((<$>))

atoi x = read  x :: Int
main = do
  (a:b:_) <- ( map atoi ) <$> words <$> getLine
  let (l,r) = solve a b
  putStrLn $ (show l) ++ " " ++ (show r) 

solve :: Int -> Int -> (Int, Int)
solve a b = (f a b, g a b)
  where
    f x y = a * b
    g x y = x * 2 + y * 2

Measured memory_bytes: 3544
n_switch, n_light = [int(i) for i in input().split()]
l_s = [[int(i)-1 for i in input().split()][1:] for _ in range(n_light)]
pp = [int(i) for i in input().split()]

ans = 0
for bit in range(1 << n_switch):
    on_switch = {i for i in range(n_switch) if (bit >> i) & 1}
    for i, p in enumerate(pp):
        ok = set(l_s[i]).intersection(on_switch)
        if len(ok) % 2 != p:
            break
    else:
        ans += 1

print(ans)


Measured memory_bytes: 41692
#include <bits/stdc++.h>
using namespace std;
int conv1(char c){
  if ('a' <= c && c <= 'z'){
    return c - 'a';
  }
  if ('A' <= c && c <= 'Z'){
    return c - 'A' + 26;
  }
}
char conv2(int x){
  if (x < 26){
    return x + 'a';
  } else {
    return x - 26 + 'A';
  }
}
int main(){
  while (1){
    int n;
    cin >> n;
    if (n == 0){
      break;
    }
    vector<int> k(n);
    for (int i = 0; i < n; i++){
      cin >> k[i];
    }
    string s;
    cin >> s;
    int m = s.size();
    for (int i = 0; i < m; i++){
      s[i] = conv2((conv1(s[i]) - k[i % n] + 52) % 52);
    }
    cout << s << endl;
  }
}


Measured memory_bytes: 3144
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <math.h>
#include <map>
#include <numeric>
using namespace std;
typedef long long int ll;

int d[]={10,50,100,500};

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	bool hi=0;
	while(1){
		int n; cin >> n;
		if(n==0)break;
		if(hi)cout << endl;
		int a[4];
		int r[4]={};
		int sum=0;
		for(int i=0;i<4;i++){
			cin >> a[i];
			sum+=d[i]*a[i];
		}
		sum-=n;
		for(int i=3;i>=0;i--){
			while(sum>=d[i]){
				sum-=d[i];
				r[i]++;
			}
		}
		for(int i=0;i<4;i++){
			int x=a[i]-r[i];
			if(x>0){
				cout << d[i] << " " << x << endl;
			}
		}
		hi=1;
	}
}


Measured memory_bytes: 3084
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <bitset>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
clock_t __my_start_clock = clock();
#else
#define eprintf(...)
#endif

#define TIMESTAMP(x) eprintf("["#x"] Time : %.3lf s.\n", (clock() - __my_start_clock)*1.0/CLOCKS_PER_SEC)
#define TIMESTAMPf(x,...) eprintf("[" x "] Time : %.3lf s.\n", __VA_ARGS__, (clock() - __my_start_clock)*1.0/CLOCKS_PER_SEC)

#define db(x) cerr << #x << " = " << x << endl
#define db2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")\n";
#define db3(x, y, z) cerr << "(" << #x << ", " << #y << ", " << #z << ") = (" << x << ", " << y << ", " << z << ")\n"
#define dbv(a) cerr << #a << " = "; for (auto xxxx: a) cerr << xxxx << " "; cerr << endl


using namespace std;

#ifdef LOCAL
static struct __timestamper {
  string what;
  __timestamper(const char* what) : what(what){};
  __timestamper(const string& what) : what(what){};
  ~__timestamper(){
    TIMESTAMPf("%s", what.data());
	}
} __TIMESTAMPER("end");
#else 
struct __timestamper {};
#endif

typedef long long ll;
typedef long double ld;

vector<int> ans;

void gen(int &cur, int mask) {
  if (mask == 0) return;
  int bit = mask & ~(mask - 1);
  gen(cur, mask ^ bit);
  ans.push_back(cur ^= bit);
  gen(cur, mask ^ bit);
}

int main() {
#ifdef LOCAL
  freopen("c.in", "r", stdin);
  freopen("c.out", "w", stdout);
#endif

  int n, a, b;
  while (scanf("%d%d%d", &n, &a, &b) == 3) {
    ans.clear();
    {
      int x = a ^b;
      if (__builtin_popcount(x) % 2 != 1) {
        printf("NO\n");
        continue;
      }
    }
    int cur = a;
    int mask_all = (1 << n) - 1;
    ans.push_back(a);

    while (mask_all) {
      int x = cur ^ b;
      assert((x & ~mask_all) == 0);
      assert(__builtin_popcount(x) % 2 == 1);
      int bit = x & ~(x - 1);

      gen(cur, mask_all ^ bit);
      ans.push_back(cur ^= bit);
      mask_all ^= bit;
    }
    assert(cur == b);

    printf("YES\n");
    for (int x : ans) {
      printf("%d ", x);
    }
    printf("\n");
#ifdef LOCAL
    assert(ans[0] == a);
    assert(ans.back() == b);
    for (int i = 0; i < (1 << n) - 1; i++) {
      int x = ans[i] ^ ans[i+1];
      assert((x & (x - 1)) == 0);
    }
    assert((int)ans.size() == (1 << n));
    sort(ans.begin(), ans.end());
    assert(unique(ans.begin(), ans.end()) == ans.end());
#endif
  }

  return 0;
}


Measured memory_bytes: 1656
#include<stdio.h>
int main()
{
    int n,i,r,x,y;
    scanf("%d",&n);
    int a[n];
    for(i=0; i<n; i++)
    {
        scanf("%d",&a[i]);
    }
    for(i=0; i<n; i++)
    {
        r=a[i]%2;
        if(r==0)
        {
            x=a[i]%3;
            y=a[i]%5;
            if((x!=0)&&(y!=0))
            {
                printf("DENIED");
                return 0;
            }
        }
    }
    printf("APPROVED");
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second
 
const int mx=100010;
const ll mod=1e9+7;

int main(){  
  int k;
  cin >> k;
  vector<ll> a(k);
  rep(i,k) cin >> a[i];
  reverse(a.begin(),a.end());

  ll cnt = 2;
  ll ans = 2;
//  if(a[0]!=2){ cout << -1 << endl; return 0; }
  rep(i,k){
    if(cnt%a[i]!=0 && cnt/a[i]==ans/a[i]){
      cout << -1 << endl; return 0;
    }
    cnt = ((cnt-1)/a[i])*a[i]+a[i];
    ans = (ans/a[i])*a[i] + a[i]-1;
  }
  cout << cnt << " " << ans << endl;
  return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int a[105];
int cnt[105];
int main(){
    /// input
    int n,x;
    cin>>x>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    /// process
    for(int i=0;i<n;i++){
        cnt[a[i]] = 1;
    }
    int dis = 1e9;
    int ans = 1000;
    for(int i=0;i<=101;i++){
        int found = cnt[i];
        if(found==1)continue;
        int tmp = abs(x-i);
        if(tmp<dis){
            dis = tmp;
            ans = i;
        }
    }
    /// output
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define repp(i,l,r)for(long long i=(l);i<(r);i++)
#define rep(i,n) for (long long i = 0; i < (n); ++i)
#define per(i,n) for (long long i = (n); i >= 0; --i)
const int INF = 2147483647;//int max
const long long int MOD = 1000000007;
using namespace std;
using ll = long long;
using P = pair<int,int>;
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; }
//ミョ(-ω- ?)
int main() {
    ll n,m;
    cin >> n >> m;
    priority_queue<ll> que;
    rep(i,n){
        ll a = 0;
        cin >> a;
        que.push(a);
    }
    while (m--){
        ll t = que.top();
        que.pop();
        que.push(t/2);
    }
    ll ans = 0;
    while(n--){
        ans += que.top();
        que.pop();
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
    string S;
    cin>>S;int err=753;
    for(int i=0;i<=S.size()-3;i++){
        int X=(S[i]-'0')*100+(S[i+1]-'0')*10+S[i+2]-'0';
        err=min(abs(X-753),err);
    }cout<<err<<endl;
}

Measured memory_bytes: 256
/*
 * A.cpp
 *
 *  Created on: 2020/06/21
 *      Author: admin
 */


#include <iostream>


using namespace std;


int main(){
	char s;
	cin >> s;
	if(isupper(s)) {
		cout  << 'A';
	}else{
		cout  << 'a';
	}
	return 0;
}



Measured memory_bytes: 3632
#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 ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int a,b;
	string s,t,u;
	cin >> s >> t >> a >> b >> u;
	if(u==s) a--;
	else b--;
	cout << a << " " << b << '\n';
	return 0;
}



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

#define FOR(i, j, k) for(int i=j ; i<k ; i++)
#define REP(i, j) FOR(i, 0, j)
typedef long long int ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;

int main() {

    int N; cin >> N;
    if ( N >= 1000  ) cout << "ABD" << endl;
    else cout << "ABC" << endl;

    return 0;
}


Measured memory_bytes: 256
/*
2
1000000000 1000000000
2 1 1000000000
*/
#include <bits/stdc++.h>
using namespace std;
void print() { cout << '\n'; } template<class T, class ...U> void print(T x, U ...y) { cout << x << ' '; print(y...); }
typedef long long ll; const int N = 2e5 + 5, M = 1e9 + 7; typedef vector<int> vi; typedef vector<vi> vii; void Main();
int main(int argc, char **argv) {
  ios::sync_with_stdio(0), cin.tie(0); cout << setprecision(10) << fixed;
  #ifdef Zmm
  freopen((string(*(argv)).substr(2, string(*(argv)).size() - 6) + string(".cpp")).c_str(), "r", stdin); string x; cin >> x;
  #endif
  Main();
}
struct edge {
  ll v, w;
  bool operator<(const edge &e)const { return w > e.w; }
};
vector<edge> G[N], g[N];
namespace DFZ {
  int x[N], siz[N], RT, RTMAX, vis[N], SIZE;
  void getrt(int u, int fa) {
    int mx = 0;
    siz[u] = 1;
    for (edge &e : G[u]) if (e.v != fa && !vis[e.v]) {
      getrt(e.v, u);
      siz[u] += siz[e.v];
      mx = max(mx, siz[e.v]);
    }
    mx = max(mx, SIZE - siz[u]);
    if (mx < RTMAX) RTMAX = mx, RT = u;
  }
  int rt;
  pair<ll, int> diss[N];
  ll DIS;
  void getdis(int u, int fa, ll dis) {
    if (dis + x[u] < DIS) DIS = dis + x[u], rt = u;
    for (edge &e : G[u]) if (e.v != fa && !vis[e.v]) {
      getdis(e.v, u, dis + e.w);
    }
  }
  void build(int u, int fa, ll dis) {
    if (rt != u) g[rt].push_back({u, dis + x[u]}), g[u].push_back({rt, dis + x[u]});
    for (edge &e : G[u]) if (e.v != fa && !vis[e.v]) build(e.v, u, dis + e.w);
  }

  void dfz(int u) {
    vis[u] = 1;
    DIS = 0x3f3f3f3f3f3f3f3f;
    getdis(u, u, 0);
    build(u, u, DIS);
    for (edge &e : G[u]) if (!vis[e.v]) {
      RT = RTMAX = SIZE = siz[e.v];
      getrt(e.v, u);
      dfz(RT);
    }
  }
}
namespace Prim {
  bool vis[N];
  ll dis[N];
  ll prim(int n) {
    for (int i = 1; i <= n; i++) dis[i] = 0x3f3f3f3f3f3f3f3f;
    ll ans = 0;
    priority_queue<edge> q;
    q.push({1, 0});
    while (!q.empty()) {
      edge e = q.top();
      q.pop();
      if (vis[e.v]) continue;
      vis[e.v] = 1, ans += e.w;
      for (edge &ee : g[e.v]) if (!vis[ee.v]) {
        if (dis[ee.v] > ee.w) dis[ee.v] = ee.w, q.push({ee.v, ee.w});
      }
    }
    return ans;
  }
}
void Main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> DFZ::x[i];
  for (int i = 1, u, v, w; i < n; i++) cin >> u >> v >> w, G[u].push_back({v, w}), G[v].push_back({u, w});
  DFZ::RT = DFZ::RTMAX = DFZ::SIZE = n;
  DFZ::getrt(1, 1);
  DFZ::dfz(DFZ::RT);
  cout << Prim::prim(n) << '\n';
}

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

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int MD = (int)1e9 + 7; typedef vector<ll> VL;
void dbg(){ cerr << "\n"; }  template <class T, class ...T2> void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }
template <class T, class T2> void amax(T& a,T2 b){ if(a < b) a = b;}


int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	int h, w, k;
	cin >>h >>w >>k;
	vector<string> s(h);
	rep(i, h) cin >>s[i];
	vector<VI> ba(h, VI(w));
	rep(i,h) rep(j,w) ba[i][j] = s[i][j] -'0';
	int res = 1<<28;
	rep(i,1<<(h-1)){
		int tsu = 0;
		vector<int> cv(h);
		rep(j, h){ cv[j] = tsu; if((i>>j)& 1) tsu++; }
		if(tsu >= res) continue;
		vector<int> cdy(tsu+1,0);
		rep(x, w){
			bool addsw=false;
			vector<int> now1(tsu+1,0);
			rep(y, h){
				now1[cv[y]] += ba[y][x];
				if(now1[cv[y]] > k) goto lastloop;
				cdy[cv[y]] += ba[y][x];
				if(cdy[cv[y]] > k) addsw=true;
			}
			if(addsw){
				tsu++;
				cdy = now1;
			}
		}
		res = min(res, tsu);
		lastloop: ;
	}
	cout << res <<"\n";
	return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, a[100007], b[100007], s[200007], sum[100007], sa, sb, res;
int read()
{
	int num = 0;
	char c = getchar();
	while (c < '0' || c>'9')c = getchar();
	while (c >= '0' && c <= '9')num = num * 10 + c - '0', c = getchar();
	return num;
}
signed main()
{
	n = read();
	for (int i = 1; i <= n; i++)
	{
		a[i] = s[2 * i - 1] = read();
		b[i] = s[2 * i] = read();
		sa += a[i];
		sb += b[i];
	}
	res = min(sa, sb);
	sort(s + 1, s + 2 * n + 1);
	for (int i = 1; i <= n; i++)
		sum[i] = sum[i - 1] + s[i];
	for (int i = 1; i <= n; i++)
	{
		int x = a[i], y = b[i];
		if (x > y)swap(x, y);
		if (lower_bound(s + 1, s + 2 * n + 1, x) - s <= n - 2)
			if (lower_bound(s + 1, s + 2 * n + 1, y) - s <= n - 1)
				res = min(res, sum[n]);
			else res = min(res, sum[n - 1] + y);
		else res = min(res, sum[n - 2] + x + y);
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 4096
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int S = sc.nextInt();
        int W = sc.nextInt();
        
        String safety = null;
        
        if(W >= S){
            safety = "unsafe";
        } else {
            safety = " safe";
        }
        
        System.out.println(safety);
    }
}


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

using namespace std;
using lli = int_fast64_t;
using ulli = unsigned long long;
#define debug(x) cerr << #x << " : " << x << endl
#define debugv(x) cerr << #x << " : {";for(auto value_of_x:x){ cerr << value_of_x << ", ";}cerr << endl
#define debugst(x) auto xt = copy(x);cerr << #x << " : {";for(int i=0;i<x.size();i++){ cerr << xt.top() << ", ";xt.pop();}cerr << endl
#define debugvp(x) cerr << #x << " : {";for(auto value_of_x:x){ cerr << value_of_x.first << " : " << value_of_x.second << ", ";}cerr << endl

constexpr lli MOD = (lli)1e9 + 7;
constexpr lli LIMIT = 1000000000000000000 * 5;
const lli e18 = pow(10,18);

int main() {
	int N;
	cin >> N;
	lli ans = 1;
	vector<lli> A(N);
	bool zero = false;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		if (A[i] == 0)zero = true;
	}
	if (zero) {
		cout << 0 << endl;
		return 0;
	}
	for (int i = 0; i < N; i++) {
		if (ans > e18 / A[i]) {
			cout << -1 << endl;
			return 0;
		}
		ans *= A[i];
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 4036
#include "bits/stdc++.h"
#include <random>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int D;

int c[27];
int s[366][27];
int last[27];

const ll INF = 1e9;

vector<int> ans;
ll ans_score;

ll calcScore(){
    rep(i,27) last[i] = 0;
    ll score = 0;
    for(int d = 1; d <= D; ++d){
        int t = ans[d];
        score += s[d][t];
        last[t] = d;
        for(int i = 1; i <= 26; ++i){
            score -= c[i] * (d - last[i]);
        }
    }
    return score;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> D;
    for(int i = 1; i <= 26; ++i) cin >> c[i];
    for(int i = 1; i <= D; ++i){
        for(int j = 1; j <= 26; ++j){
            cin >> s[i][j];
        }
    }
    ans_score = -INF;
    //greedy
    /*
    for(int d = 1; d <= D; ++d){
        ll score = -INF;
        int id = 1;
        for(int t = 1; t <= 26; ++t){
            ll new_score = s[d][t];
            last[t] = d;
            for(int i = 1; i <= 26; ++i){
                new_score -= c[i] * (d - last[i]);
            }
            if(score < new_score){
                id = t;
                score = new_score;
            }
        }
        ans.push_back(id);
        ans_score += score;
    }
    */
    ans.resize(D, 1);
    ans_score = calcScore();
    //local search
    std::random_device rnd;
    std:: mt19937 mt(rnd());
    std::uniform_int_distribution<> randD(1,D);
    std::uniform_int_distribution<> randA(1,26);
    rep(_,10000){
        int d = randD(mt);
        int q = randA(mt);
        //cout << d << " " << q << endl;
        int old = ans[d];
        ans[d] = q;
        ll score = calcScore();
        if(ans_score > score){
            ans[d] = old;
        }
        else{
            ans_score = score;
        }
    }
    rep(i,D) cout << ans[i] << endl;
    return 0;
}


Measured memory_bytes: 3728
# -*- coding: utf-8 -*-
from heapq import heappop, heappush
def solve(): 
    N = int(input())
    edges = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        edges[u].append((v, w&1))
        edges[v].append((u, w&1))

    D = [-1]*(N+1)
    hq = [(0,1)]
    checked = set()
    while hq:
        c, u = heappop(hq)
        checked.add(u)
        D[u] = c
        for v, w in edges[u]:
            if not v in checked:
                heappush(hq, (c^w, v))

    res = '\n'.join(map(str, D[1:]))
    return str(res)

if __name__ == '__main__':
    print(solve())




Measured memory_bytes: 46124
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define pb push_back
#define ub upper_bound
#define lb upper_bound
#define mp make_pair
#define F first
#define S second
#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()
#define RALL(a) (a).rbegin(),(a).rend()
#define SORT(c) sort((c).begin(),(c).end())
#define ve vector
#define vi vector<int>
#define vp vector<pair<int,int>>
#define vvi vector<vector<int>>
 
typedef long long ll;
const ll INF = LLONG_MAX - 100;
const ll mod = 1e9 + 7;
const int MAX_N = 2e5 + 5;
int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};
vector<ll> prime;
 
int fac[MAX_N], inv[MAX_N];
 
template <class T = ll> T in() {T x; cin >> x; return (x);}
void DEBUG(vector<int> a) {for(int i=0;i<a.size();i++)cout<<a[i]<<" ";cout<<endl;}
void EMP(int x) {cout<<"!!!"<<x<<"!!!"<<endl;}
ll GCD(ll a, ll b) {ll c; while (b != 0) {c = a % b; a = b; b = c;}return a;}
ll LCM(ll a, ll b) {return a * b / GCD(a, b);}
ll POW(ll a, ll b, bool usemod = true) {ll c = 1LL; while (b > 0) {if (b & 1LL) {if(!usemod)c*=a;else c = a * c%mod;}if (!usemod) a*=a;else a = a * a%mod; b >>= 1LL;}return c;}
void _nCr() {fac[0] = 1LL; for (int i = 1LL; i < MAX_N; i++) {fac[i] = fac[i - 1LL] * i%mod;}for (int i = 0; i < MAX_N; i++) {inv[i] = POW(fac[i], mod - 2);}}
ll nCr(ll n, ll r) {return (fac[n] * inv[r] % mod)*inv[n - r] % mod;}
void PRI(ll n) {bool a[n + 1LL]; for (int i = 0; i < n + 1LL; i++) {a[i] = 1LL;}for (int i = 2; i < n + 1LL; i++) {if (a[i]) {prime.pb(i); ll b = i; while (b <= n) {a[b] = 0; b += i;}}}}
template <typename T> T chmin(T& a, T b) {if(a>b)a=b;return a;}
template <typename T> T chmax(T& a, T b) {if(a<b)a=b;return b;}

bool solve() {
	int n; cin >> n;
	int p[n]; REP (i,n) cin >> p[i];
	int ans = 0;
	FOR (i,1,n-1) {
		if (p[i-1] < p[i] && p[i] < p[i+1]) ans++;
		if (p[i-1] > p[i] && p[i] > p[i+1]) ans++;
	}
	cout << ans << endl;
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	solve();
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
using namespace std;
// ===================== MANASH =================== //

int n,m;

void test() {

	cin >> n;
	int k; cin >> k;
	vector<int> v(n);
	for( int &x : v ) cin >> x;
	sort(v.begin(),v.end(),greater<int>());
	int x = 0;
	for( int i = k; i < n; i++) {
		x += v[i];
	}

	cout << x;

}

signed main() {

	#ifdef LOCAL
	freopen("input.txt","r",stdin);
	#endif

	test();
	cout << '\n';
	return 0;

}

Measured memory_bytes: 4820
#include<bits/stdc++.h>
using namespace std;
int main(){
  #define int long
  int n,m;
  cin>>n>>m;
  if(n>=m){cout<<0;return 0;}
  vector<int> x(m),y(m-1);
  for(int i=0;i<m;++i)cin>>x[i];
  sort(x.begin(),x.end());
  for(int i=0;i<m-1;++i)y[i]=x[i+1]-x[i];
  sort(y.begin(),y.end());
  for(int i=1;i<m;++i)y[i]+=y[i-1];
  sort(y.begin(),y.end(),greater<int>());
  cout<<y[n-1];
  return 0;
}

Measured memory_bytes: 1792
s = input()
n = len(s)
ans = 0
ct = 0
for i in range(n):
  
  if s[i] == 'A': ans  += 1
  elif s[i] == 'T': ans  += 1
  elif s[i] == 'C': ans  += 1
  elif s[i] == 'G': ans  += 1
  else: ans = 0
  ct = max(ct,ans)
print(ct)

Measured memory_bytes: 3060
word1 = input()
word2 = input()

NK = word1.split()
NKs = [0,0]
N = int(NK[0])
K = int(NK[1])
score = word2.split()
scli = [0]*N

for i in range(N):
    scli[i] = int(score[i])

#for j in range(K):
#    test *= scli[j]
#ue ga i-1 banme

for s in range(N-K):
    if scli[s] < scli[K+s]:
        print('Yes')
    else:
        print('No')

Measured memory_bytes: 33100