akhauriyash/Code-Regression huggingface dataset:
#!/mnt/c/Users/moiki/bash/env/bin/python
# FROM : https://atcoder.jp/contests/dp/submissions/4017206
# N,M = map(int, input().split())
N = int(input())
from collections import Counter
a = Counter( map(int, input().split()))


#1,2,3
A,B,C = (a[i] for i in range(1,4))

# dpA,B,C

# dp = [ [ [0] * (C+1) 
#            for _ in range(B+C+1)
#        ]
#            for _ in range(A+B+C+1) 
#      ]

dp = [ [ [0]*(A+B+C+1) for _ in range(B+C+1)]
        for _ in range(C+1) ] 

for c in range(C+1):
    for b in range(B+C+1-c):
        for a in range(A+B+C+1-b-c):
            # if a == b == c == 0:
            #     continue

            try: 
                dp[c][b][a] = (
                        ( a * ( dp[c][b][a-1]   if a else 0)  ) + 
                        ( b * ( dp[c][b-1][a+1] if b else 0)  ) +
                        ( c * ( dp[c-1][b+1][a] if c else 0)  ) + N 
                       ) / ( a+b+c ) 
                # dp[a][b][c] = (
                #         ( a * ( dp[a-1][b][c]   if a else 0)  ) + 
                #         ( b * ( dp[a+1][b-1][c] if b else 0)  ) +
                #         ( c * ( dp[a][b+1][c-1] if c else 0)  ) + N 
                #        ) / ( a+b+c ) 
            except:
                continue

print(dp[C][B][A])
# print(dp[A][B][C])


Measured memory_bytes: 510344
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef pair<int, int> P;
int main(){
    int n;
    cin >> n;
    vector<int> v1(n);
    rep(i, n){
        cin >> v1[i];
    }

    map<int, int> mp1, mp2;
    rep(i, n){
       if(i % 2 == 0){
           mp1[v1[i]]++;
       }else{
           mp2[v1[i]]++;
       }
    }
    P p;
    p.second = 0;
    bool even = true;
    for(auto m : mp1){
        if(m.second > p.second){
            p.second = m.second;
            p.first = m.first;
        }
    }
    for(auto m : mp2){
        if(m.second > p.second){
            p.second = m.second;
            p.first = m.first;
            even = false;
        }
    }
    int ans = n/2 - p.second;
   // cout << p.first << " "<<p.second << endl;
    p.second = 0;
    int num1 = p.first;
    
    for(auto m : mp2){
        if(m.second > p.second && m.first != num1){
            p.second = m.second;
            p.first = m.first ;
        }
    }
    for(auto m : mp1){
        if(m.second > p.second && m.first != num1){
            p.second = m.second;
            p.first = m.first;
        }
    }
    
   // cout << p.second << endl;

    ans += n/2 - p.second;
    cout << ans<< endl;
}

Measured memory_bytes: 5376
#include <bits/stdc++.h>
using namespace std;
#define rep0(i,n) for(ll (i) = 0; (i) < (n); ++(i))
#define rrep0(i,n) for(ll (i) = (n) - 1; (i) >= 0; --(i))
#define rep1(i,n) for(ll (i) = 1; (i) <= (n); ++(i))
#define rrep1(i,n) for(ll (i) = (n); (i) >= 1; --(i))
#define nfor(i,a,b) for(ll (i) = (a); (i) < (b); ++(i))
#define rnfor(i,a,b) for(ll (i) = (a) - 1; (i) >= (b); --(i))
#define ll long long
#define mod (1000000007)
#define pf(x) cout << (x) << endl
#define all(x) (x).begin(),(x).end()

ll gcd(ll a,ll b){
    if(a < b)swap(a, b);
    if(b == 0) return a;
    return gcd(b,a%b);
}

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

ll factorial(ll n){
    ll t = 1;
    rep1(i, n)t *= i;
    return t;
}

ll combinations(ll n, ll k) {
    ll r = 1;
    rep1(i, k)r = r * n-- / i;
    return r;
}

int main(){
    ll n,m;
    cin >> n >> m;
    vector<pair<ll, ll>> x(n);
    rep0(i, n){
        ll a,b;
        cin >> a >> b;
        x[i] = make_pair(a, b);
    }
    sort(all(x));
    priority_queue<ll> q;
    ll cnt = 0,ans = 0;
    rep1(i, m){
        nfor(j, cnt, n){
            if(x[j].first != i){
                cnt = j;
                break;
            }
            q.push(x[j].second);
        }
        if(!q.empty()){
            ans += q.top();
            q.pop();
        }
    }
    pf(ans);
    return 0;
}


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

int main() {
	int W, H, x, y, r;
	cin >> W >> H >> x >> y >> r;
	if (x - r >= 0 && x + r <= W && y - r >= 0 && y + r <= H)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 3120
(defun compare-hex (a b c)
  (cond ((< (digit-char-p a 16) (digit-char-p c 16)) "<")
        ((> (digit-char-p a 16) (digit-char-p c 16)) ">")
        ((= (digit-char-p a 16) (digit-char-p c 16)) "=")))

(format t "~A~%" (compare-hex (read-char) (read-char) (read-char)))

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

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); ++i)

int main(){
  int n, l;
  cin >> n >> l;

  vector<string> v(n);
  rep(i, n) cin >> v[i];

  sort(v.begin(), v.end());

  string ans = "";
  rep(i, n) {
    ans += v[i];
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
N ,K = input().split()
list1=[]
for i in range(int(K)):
    new = input()
    list2= list(input().split())
    for  j in range(int(new)):
        list1.append(list2[j])
list1= set(list1)
length = len(list1)
print(int(N) - length)

Measured memory_bytes: 67680
#include<stdio.h>

int main(void){
  int l , r;
  scanf("%d %d",&l,&r);
  
  int ans , wl , wr;
  
  wl = l%2019;
  wr = r%2019;
  ans = 2019*2019;
  
  if(r-l >= 2019){
    ans = 0;
  }
  else{
    for(int i = wl;i < wr;i ++){
      for(int j = i+1;j <= wr;j ++){
        if((i*j)%2019 < ans){
          ans = (i*j)%2019;
        }
      }
    }
  }
 
  printf("%d\n",ans);
  
  return 0;
}

Measured memory_bytes: 128
args = input().split()
stack = []

def cal_with_operator(b, a, operator):
    return eval('{} {} {}'.format(a, operator, b))

for s in args:
    if s == '+': stack.append(cal_with_operator(stack.pop(), stack.pop(), '+'))
    elif s == '-': stack.append(cal_with_operator(stack.pop(), stack.pop(), '-'))
    elif s == '*': stack.append(cal_with_operator(stack.pop(), stack.pop(), '*'))
    elif s == '/': stack.append(cal_with_operator(stack.pop(), stack.pop(), '/'))
    else : stack.append(s)

print(stack[0])


Measured memory_bytes: 5568
#include <bits/stdc++.h>
#define mk make_pair
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
struct pnt{
  int v, x, y;
};
bool operator < (pnt a, pnt b){
  return a.v>b.v;
}
pnt mkk(int x, int y, int z){
  pnt tmp;
  tmp.v=x;
  tmp.x=y;
  tmp.y=z;
  return tmp;
}
int dx[4]={0, 0, 1, -1}, dy[4]={1, -1, 0, 0};
string s[100];
int dis[100][100];
bool vis[100][100];
int main(){
  int h, w, black;
  while(cin>>h>>w){
    black=0;
    memset(vis, 0, sizeof vis);
    for(int i=0; i<h; ++i){
      cin>>s[i];
      for(int j=0; j<w; ++j)
        if(s[i][j]=='#')
          ++black;
    }
    priority_queue <pnt> q;
    q.push(mkk(1,0,0));
    pnt tp;
    int x, y;
    while(!q.empty()){
      tp=q.top();
      q.pop();
      if(vis[tp.x][tp.y])
        continue;
      vis[tp.x][tp.y]=1;
      dis[tp.x][tp.y]=tp.v;
      for(int i=0; i<4; ++i){
        x=tp.x+dx[i];
        y=tp.y+dy[i];
        if(x<0||y<0||x>=h||y>=w)
          continue;
        if(s[x][y]=='#')
          continue;
        if(!vis[x][y]){
          q.push(mkk(tp.v+1, x, y));
        }
      }
    }
    if(!vis[h-1][w-1]){
      cout<<-1<<endl;
    }
    else{
      int tmp=h*w;
      tmp-=dis[h-1][w-1];
      tmp-=black;
      cout<<tmp<<endl;
    }
  }
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    rep(i, n) a[i]--;
    vector<int> idx(n);
    rep(i, n) idx[a[i]] = i;
    ll ans = 0;
    set<int> s;
    for (int x = n - 1; x >= 0; --x) {
        int i = idx[x];
        ll c = 0;
        {  // calc c
            s.insert(i);
            vector<int> l(2, -1);
            vector<int> r(2, n);
            {  // calc l
                auto it = s.find(i);
                rep(j, 2) {
                    if (it == s.begin()) break;
                    --it;
                    l[j] = *it;
                }
            }
            {  // calc r
                auto it = s.find(i);
                rep(j, 2) {
                    ++it;
                    if (it == s.end()) break;
                    r[j] = *it;
                }
            }
            vector<int> ls(2);
            ls[0] = i - l[0];
            ls[1] = l[0] - l[1];
            vector<int> rs(2);
            rs[0] = r[0] - i;
            rs[1] = r[1] - r[0];
            c = (ll)ls[0] * rs[1] + (ll)ls[1] * rs[0];
        }
        ans += c * (x + 1);
    }
    std::cout << ans << endl;

    return 0;
}

Measured memory_bytes: 5760
from sys import stdin
def ip(): return [int(i) for i in stdin.readline().split()]
def sp(): return [str(i) for i in stdin.readline().split()]



A = str(input())
ans = 0
curr = 0
for i in A:
    if i == 'R':
        curr += 1
        ans = max(ans, curr)
    else:
        curr = 0
print(ans)

Measured memory_bytes: 9120
s = gets.chomp.split("")
if s.length == 26
    i = 25
    a = []
    while(i>0)
        a << s[i]
        break if s[i-1] < s[i]
        a << s[i-1]
        i -= 1
    end
    if i == 0
        puts -1
    else
        b = a.select{|v| v > s[i-1]}.sort
        puts s[0,i-1].join + b[0]
    end
else
    a = ('a'..'z').to_a
    s.each {|v| a.delete(v)}
    puts s.join + a[0]
end

Measured memory_bytes: 3836
using System;
using System.Collections;
class Program{
  static void Main(){
    string X = Console.ReadLine();
    ArrayList al = new ArrayList();
    for (int i = 0;i < X.Length;i++){
      if (X[i] == 'S')
        al.Add(X[i]);
      if (X[i] == 'T' && al.Count != 0 && (char)al[al.Count - 1] == 'S')
        al.RemoveAt(al.Count - 1);
      else if (X[i] == 'T')
        al.Add(X[i]);
    }
    Console.WriteLine(al.Count);
  }
}


Measured memory_bytes: 23516
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep2(i,m,n) for (int i = m; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
template<class T> void chmin(T &a, const T &b) noexcept { if (b < a) a = b;}
template<class T> void chmax(T &a, const T &b) noexcept { if (a < b) a = b;}
template<class T> void drop(const T &x) { std::cout<<x<<endl; exit(0);}
void debug_out() { std::cout << "\n";}
template<class T, class... Args> void debug_out(const T &x, const Args &... args) { std::cout<<x<< " "; debug_out(args...);}
#ifdef _DEBUG
  #define debug(...) debug_out(__VA_ARGS__)
#else
  #define debug(...) 
#endif

struct InitIO{
  InitIO() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
  }
}init_io;

int main() {
  int a;
  cin >> a;
  int ans = a + a*a + a*a*a;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3604
#include <iostream>
#include <array>
#include <vector>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <set>

using namespace std;

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

const int INF=1<<30;
const LL MOD=1000000007;

LL gcd(LL a,LL b){
    if(b==0)return a;

    return gcd(b,a%b);
}

int main(){
    LL n,w;
    cin>>n>>w;
    vector<LL> v[4];

    LL w1;
    for(LL i=0;i<n;++i){
        LL ww,v2;
        cin>>ww>>v2;
        if(i==0)w1=ww;
        v[ww-w1].push_back(v2);
         }
    for(int i=0;i<4;++i){
        sort(v[i].begin(),v[i].end());
        v[i].push_back(0);
        reverse(v[i].begin(),v[i].end());
        for(LL j=1;j<v[i].size();++j){
            v[i][j]+=v[i][j-1];
        }
    }
    LL ans=0;
    for(LL i=0;i<v[0].size();++i){
        for(LL j=0;j<v[1].size();++j){
            for(LL k=0;k<v[2].size();++k){
                for(LL l=0;l<v[3].size();++l){
                    if(w>= (i*w1+j*(w1+1)+k*(w1+2)+l*(w1+3))){
                        ans=max(ans,(v[0][i]+v[1][j]+v[2][k]+v[3][l]));
                    }
                }
            }
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

using Lint=long long;

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

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

    auto down=[&](int k)
    {
        for(;2*k+1<N;){
            int j=2*k+1;
            if(j+1<N and a[j+1]>a[j]) j++;
            if(a[j]<=a[k]) break;
            swap(a[k],a[j]);
            k=j;
        }
    };
    for(int i=N-1;i>=0;i--) down(i);

    for(int i=0;i<N;i++) cout<<' '<<a[i];
    cout<<endl;
    return 0;
}


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

bool solve() {
    ll N;
    cin >> N;
    ll cnt = 0;
    for(ll i = 0; i < N; i++) {
        string s;
        cin >> s;
        if(s == "A") {
            cnt++;
        } else {
            if(cnt == 0) return false;
            cnt--;
        }
    }
    return cnt == 0;
}

int main() {
    cout << (solve() ? "YES" : "NO") << endl;
    return 0;
}



Measured memory_bytes: 3164
#include<bits/stdc++.h>
#define LL long long
#define REP(i,n) for(int i=0;i<(n);++i)
#define PER(i,n) for(int i=n-1;i>=0;--i)
#define REPA(i,n) for(int i=1;i<(n);++i)
#define foreach(i, n) for(auto &i:(n))
#define PII pair<int,int>
#define PLI pair<long long, int>
#define PLL pair<long long, long long>
#define MOD ((LL)1e9+7) 
#define INF ((int)1e9+7)
#define INFLL ((LL)1e18)
#define ALL(x) (x).begin(),(x).end()
#define BIT(x) (1LL << (x))
using namespace std;

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

LL modpow(LL x, LL b){
	LL res = 1;
	while(b){
		if(b&1)res = res * x % MOD;
		x = x * x % MOD;
		b>>=1;
	}
	return res;
}

LL modinv(LL x){
	return modpow(x, MOD-2);
}

int main(){
	int N, K;
	cin >> N >> K;
	vector<bool> used(N, false);
	LL sum = 0;
	LL ans = 0;
	priority_queue<LL, vector<LL>, greater<LL>> pq;
	LL val = 0;
	vector<PLL> line(N);
	foreach(i, line)cin>>i.second>>i.first;
	sort(ALL(line), greater<PLL>());
	REP(i, N){
		if(i>=K){
			if(pq.empty())break;
			sum -= pq.top();
			pq.pop();
		}
		if(!used[line[i].second]){
			++val;
			used[line[i].second] = true;
		}else{
			pq.push(line[i].first);
		}
		sum += line[i].first;
		chmax(ans, sum + val * val);
	}
	cout << ans << endl;
	return 0;
}


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

int main(){
  int N;
  cin>>N;
  int flag=1;
  while(flag=1){
    if(N==round(sqrt(N))*round(sqrt(N))){
      cout<<N<<endl;
      flag=0;
      return 0;
    }
    N--;
  }
  return 0;
}

    
 

Measured memory_bytes: 256
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
int main()
{
	ll a,b,c;
	scanf("%lld%lld%lld",&a,&b,&c);
	if(a%2==0||b%2==0||c%2==0)printf("0\n");
	else printf("%lld\n",min(a*b,min(b*c,c*a)));
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
	int i,j,k,n,a,data[10];
	while(cin>>n&&n) {
		for(i=0;i<10;i++) data[i]=0;
		for(i=0;i<n;i++) {
			cin>>a;
			data[a]++;
		}
		for(i=0;i<10;i++) {
			if(data[i]==0) cout<<"-";
			for(j=0;j<data[i];j++) {
				cout<<"*";
			}
			cout<<endl;
		}
	}
}

Measured memory_bytes: 3048
while True:
    h, w = map(int, input().split())
    if w+h == 0:
        break
    line = ""
    for y in range(h):
        if y == 0 or y == h-1:
            line = "#"*w
        else:
            line = "#"+"."*(w-2)+"#"
        print(line)
    print()



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

using ll = long long;
using pii = pair<int, int>;
template <class T>
using v = vector<T>;
template <class T>
using vv = v<v<T>>;
#define ALL(c) (c).begin(), (c).end()

int main()
{
    int N;
    cin >> N;
    v<int> color(8, 0);
    int free = 0;
    for (int i = 0; i < N; i++)
    {
        int a;
        cin >> a;
        if (a < 3200)
            color[a / 400] = 1;
        else
            free++;
    }

    int min_c = 0, max_c = 0;

    for (int i = 0; i < 8; i++)
    {
        min_c += color[i];
        max_c += color[i];
    }

    min_c = max(1, min_c);
    
    cout << min_c << " " << max_c + free << endl;

    return 0;
}

Measured memory_bytes: 3596
INF = 2*10**7


def main():
    N, M = (int(i) for i in input().split())
    A = []
    B = []
    C = []
    for _ in range(M):
        a, b = (int(i) for i in input().split())
        A.append(a)
        B.append(b)
        bit = 0
        for i in input().split():
            bit |= (1 << (int(i)-1))
        C.append(bit)
    dp = [[INF]*(1 << N) for _ in range(M+1)]
    dp[0][0] = 0
    for i in range(M):
        for j in range(1 << N):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            if dp[i][j] != INF:
                next_bit = j | C[i]
                dp[i+1][next_bit] = min(dp[i+1][next_bit], dp[i][j] + A[i])
    ans = dp[-1][-1]
    if ans == INF:
        print(-1)
    else:
        print(ans)
    # print(*dp, sep="\n")


if __name__ == '__main__':
    main()


Measured memory_bytes: 78552
//Sort
#include <iostream>
#include <math.h>
using namespace std;
int main(){
    int i1, i2, i3, n, minnum, d, times;
    cin >> n;
    int v[n];
    i1 = 0;
    while(1){
        cin >> v[i1];
        i1++;
        if(i1>=n)break;
    }
    times=0;
    i1=0;
    i2=0;
    while(1){
        minnum=i2;
        i2++;
        i3=i2;
        if(i2==n)break;
        while(1){
            if(v[minnum]>v[i3]){
                minnum=i3;
            }
        i3++;
        if(i3>=n)break;
        }
        if(v[i2-1]!=v[minnum]){
        d=v[i2-1];
        v[i2-1]=v[minnum];
        v[minnum]=d;
            times++;
    }
    }
    i1=0;
    cout << v[i1];
    while(1){
        i1++;
        if(i1>=n)break;
        cout << " " << v[i1];
    }
    cout << endl << times << endl;

    
    return 0;
}

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

int main(){
  int N;
  cin >> N;
  set<string> st;
  for(int i = 0; i < N; i++) {
    string s;
    cin >> s;
    st.insert(s);
  }
  cout << st.size() << endl;
}

Measured memory_bytes: 19220
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1000000007;
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define debug(x) cout << #x << " : " << x << endl
#define mp make_pair
#include <iostream>
#define fastinput ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);


LL POW(LL x,LL y)
{
    LL ans=1;
    LL base=x;
    while(y)
    {
        if(y&1)
        {
            ans*=base;
        }
        base=base*base;
        y=y>>1;
    }
    return ans;
}



int main()
{    
    fastinput;
    LL n,i,j,k,t,temp,tc,a,b,c;
    cin>>a>>b>>c;
    cout<<c<<" "<<a<<" "<<b<<endl; 
    


    
    return 0;
}


Measured memory_bytes: 3648
a = input()
b = input()
list1 = [["a", 0 ],["b", 0 ],["c", 0 ],["d", 0 ],["e", 0 ],["f", 0 ],["g", 0 ],["h", 0 ],["i", 0 ],["j", 0 ],
["k", 0 ],["l", 0 ],["m", 0 ],["n", 0 ],["o", 0 ],["p", 0 ],["q", 0 ],["r", 0 ],["s", 0 ],["t", 0 ],
["u", 0 ],["v", 0 ],["w", 0 ],["x", 0 ],["y", 0 ],["z", 0 ]]
list2 = [["a", 0 ],["b", 0 ],["c", 0 ],["d", 0 ],["e", 0 ],["f", 0 ],["g", 0 ],["h", 0 ],["i", 0 ],["j", 0 ],
["k", 0 ],["l", 0 ],["m", 0 ],["n", 0 ],["o", 0 ],["p", 0 ],["q", 0 ],["r", 0 ],["s", 0 ],["t", 0 ],
["u", 0 ],["v", 0 ],["w", 0 ],["x", 0 ],["y", 0 ],["z", 0 ]]
for i in range(len(a)):
    for j in range(26):
        if a[i] == list1[j][0]:
            list1[j][1] += 1
            break
for i in range(len(b)):
    for j in range(26):
        if b[i] == list2[j][0]:
            list2[j][1] += 1
            break
list3 = [list1[i][1] for i in range(26)]
list3.sort()
list4 = [list2[i][1] for i in range(26)]
list4.sort()
flag = True
for i in range(26):
    if int(list3[i]) != int(list4[i]):
        flag = False
if flag:print("Yes")
else:print("No")

Measured memory_bytes: 3888
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100000+20;
int n,dp[MAXN][3];
int main() {
	cin>>n;
	for (int i=1; i<=n; i++) {
		int a,b,c;
		cin>>a>>b>>c;
		dp[i][0]=a+max(dp[i-1][1],dp[i-1][2]);
		dp[i][1]=b+max(dp[i-1][0],dp[i-1][2]);
		dp[i][2]=c+max(dp[i-1][1],dp[i-1][0]);
	}
	cout<<max(max(dp[n][0],dp[n][1]),dp[n][2])<<'\n';
	return 0;
}


Measured memory_bytes: 1408
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
typedef long long LL;

char s[100005];
int vis[10000];

int main(){
	cin >> s + 1;
	int len = strlen(s + 1);
	for(int i = 1;i <= len;i++){
		vis[s[i]] = 1;
	}
	int flag = 0;
	for(int i = 'a';i <= 'z';i++){
		if(vis[i] == 0){
			printf("%c",i);
			flag = 1;
			break;
		}
	}
	if(flag == 0) printf("None");
}

Measured memory_bytes: 384
n = int(input())
prev_t = 0
prev_x = 0
prev_y = 0
for i in range(n):
    t, x, y=map(int, input().split())
    if abs(prev_x - x) + abs(prev_y - y) > (t - prev_t) or (abs(prev_x - x) + abs(prev_y - y) + (t - prev_t)) % 2:
        print("No")
        exit()
    prev_t = t
    prev_x = x
    prev_y = y
print("Yes")

Measured memory_bytes: 3064
N=io.read("n")
X={}
B={}
for i=1,N do
  X[i]=io.read("n")
  B[i]=X[i]
end
table.sort(B)
left=B[N//2]
right=B[N//2+1]
for i=1,N do
  if X[i]<=left then
    print(right)
  	elseif X[i]>=right then
    print(left)
  end
end


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

namespace AtCoder.At_Coder_Beginner_Contest_169
{
    class A
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            long A = long.Parse(input[0]);
            long B = long.Parse(input[1]);

            Console.WriteLine(A*B);
        }
    }
}


Measured memory_bytes: 27528
#include<stdio.h>
int main(void)
{
	int a,b,c,d,n,x,y;
	scanf("%d %d %d %d",&a,&b,&c,&d);
	n=a+b+c+d;
	x=n/60;
	y=n%60;
	printf("%d\n%d\n",x,y);
	return 0;
}


Measured memory_bytes: 2712
N = int(input())
A = list(map(int, input().split()))
A.sort()
isOK = True
BIG_PRIME = 1000000007

if N % 2: # 奇数の場合
    for i in range(0, N - 2, 2):
        if A[i] != i:
            isOK = False
            break
        if A[i + 1] != i + 2:
            isOK = False
            break
    if A[N - 1] != N - 1:
        isOK = False
    num = (N - 1) // 2
else: # 偶数の場合
    for i in range(0, N, 2):
        if A[i] != i + 1:
            isOK = False
            break
        if A[i + 1] != i + 1:
            isOK = False
            break
    num = N // 2

if isOK:
    ans = 1
    for _ in range(num):
        ans *= 2
        ans %= BIG_PRIME
    print(str(ans))
else:
    print("0")


Measured memory_bytes: 14004
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(0)
#define endl "\n"
#define int long long
typedef vector<int> vi;
#define all(x) x.begin(),x.end()
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
#define pii              pair <int,int>
#define debug(x) cerr << '>' << #x << ':' << x << endl;
typedef long long ll;
//#pragma comment(linker, "/STACK:667772160")
#define in_range(x, y, r, c) ((x >= 0 && x < r && y >= 0 && y < c))

const double eps=1e-9;
const int MOD=1e9+7;
const int N=2*1e5+30;
const int inf = 1e17+995;

template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
void boostIO() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
int32_t main() {
    boostIO();
int n;
cin>>n;
cout<<exp(n,3ll);

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define M 1<<17
using namespace std;
int g(int a,int b){return b?g(b,a%b):a;}
int N,A[M],L[M],R[M],i,ans;
int main(){
	cin>>N;
	for(i=0;i<N;i++)cin>>A[i];
	for(i=0;i<N;i++)L[i+1]=g(L[i],A[i]);
  reverse(A,A+N);
	for(i=0;i<N;i++)R[i+1]=g(R[i],A[i]);
	for(i=0;i<N;i++)ans=max(ans,g(L[i],R[N-1-i]));
	cout<<ans<<endl;
}


Measured memory_bytes: 1408
#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) a.size()
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(998244353)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
int main()
{
string s;
  cin>>s;
  map<char,int>cnt;
  for(char x:s)cnt[x]++;
  for(auto x:cnt){
    if(x.se != 2){
      cout<<"No";
      return 0;
    }
  }
  cout<<"Yes";
  
}

Measured memory_bytes: 3568
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <functional>

using namespace std;
    
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <limits>
#include <bits/stdc++.h>
using namespace std;
struct UNION{
    vector<int> par;
    vector<int> rank;
    void Union(int sz){
        par.resize(sz);
        rank.assign(sz,0);
        for(int i=0;i<sz;i++){
            par[i]=i;
        }
    }        

int find(int a){
    if(a==par[a])return a;
    return find(par[a]);
}
void unite(int a,int b){
    int root_a = find(a);
    int root_b = find(b);
    if(root_a==root_b) return;
    if(rank[root_a]>rank[root_b]){
        par[root_b] = root_a;
    }else if(rank[root_a]<rank[root_b]){
        par[root_a] = root_b;
    }else{
        rank[root_a]++;
        par[root_b] = root_a;
    }
}
};
int main(){
   UNION uni;
   int n,q;
   cin >> n >> q;
   uni.Union(n);
   for(int i=0;i < q;i++){
       int x;
       cin >> x;
       int num1,num2;
       cin >>num1 >>num2;
       if(x==0){
           uni.unite(num1,num2);
       }else{
           
           if(uni.find(num1)==uni.find(num2)){
               cout << 1 << endl;
           }else{
               cout << 0 << endl;
           }
       }
   }
}





Measured memory_bytes: 3192
import java.io.{BufferedReader, InputStreamReader}

import scala.annotation.tailrec

object Main {
  def main(args: Array[String]): Unit = {
    val in = new BufferedReader(new InputStreamReader(System.in))
    val n = in.readLine().toInt
    val ls = in.readLine().split("\\s+").map(_.toInt).sorted

    def countWhile(index: Int, cond: Int => Boolean): Int = {
      @tailrec
      def binarySearch(sIndex: Int, eIndex: Int): Option[Int] = {
        if (sIndex > eIndex) {
          None
        } else {
          val index = (eIndex + sIndex) / 2
          if (!cond(ls(index))) {
            binarySearch(sIndex, index - 1)
          } else {
            if (index == ls.length - 1) {
              Some(index)
            } else {
              if (!cond(ls(index + 1))) {
                Some(index)
              } else {
                binarySearch(index + 1, eIndex)
              }
            }
          }
        }
      }

      binarySearch(index, ls.length - 1) match {
        case Some(i) => i - index + 1
        case None => 0
      }
    }

    System.out.println(
      (for {
        ai <- 0 until ls.length - 2
        a = ls(ai)
        bi <- (ai + 1) until ls.length - 1
        b = ls(bi)
        apb = a + b
        amb = a - b
      } yield {
        countWhile(bi + 1, _ < apb)
      }).sum
    )
  }
}


Measured memory_bytes: 154580
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,m,k;
	long long ans=0;
	int a[200005]={0};
	scanf("%d",&n);
	for(int i=0;i<n;i++)cin>>a[i];
	sort(a,a+n);
	m=n/2;
	k=n%2?m:m-1;
	for(int i=n-1;m;m--,i--)ans+=a[i];
	for(int i=n-2;k;k--,i--)ans+=a[i];
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 4616
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,N) for(i=0;i<N;i++)
#define N 1000000

int f(int n){
  if(n%2 == 0) return n/2;
  else return 3*n + 1;
}

int main(void){
  int s,a;
  cin >> s;
  vector<int> L(N);
  int i;
  FOR(i,N){
    if( s == 4 || s == 2 || s == 1) break;
    s = f(s); 
  }
  cout << i + 4 << endl;
  return 0;
}

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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j;
    ll a,b,n;
    cin >> a >> b >> n;
    ll tmp = min(b-1,n);
    ll ans = tmp*a/b;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3620
#include<iostream>
using namespace std;
int main()
{
    int i,a,b;
    cin>>a>>b;
    if(a>b)
    {
        for(i=0; i<a; i++)
            cout<<b;
    }
    else if (b>=a)
    {
        for(i=0; i<b; i++)
            cout<<a;
    }
    cout<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(){
	char hoge[21];
	char *itr=hoge;

	scanf("%s",hoge);
	
	while('\0'!=*itr){
		itr++;
	}

	while(hoge!=itr){
		itr--;
		printf("%c",*itr);
	}
	printf("\n");
	return 0;
}

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

#define int long long

bool cd(int n){
	int c = 0 ;
	while(n){
		n/=10 ;
		c++ ;
	}
	return c&1 ;
}

int32_t main() {
	int n ; cin >> n ;
	int count = 0 ;
	for(int i = 1 ; i <= n ; i++) count += cd(i) ;
	cout << count ;
	return 0;
}

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

#define fi first
#define se second
#define pb push_back
#define rep(i,n) for(int i=0; i<(int)(n); i++)

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	vector< vector<int> > x(n);
	vector< vector<int> > y(n);
	int xtemp,ytemp;
	rep(i,n) {
		cin >> a[i];
		rep(j, a[i]) {
			cin >> xtemp >> ytemp;
			x[i].pb(xtemp - 1);
			y[i].pb(ytemp);
		}
	}
	bool flag;
	int max = 0;
	for (int bit = 0; bit < (1<<n); ++bit) {
		flag = true;
		rep(i,n) {
			rep(j, a[i]) {
				if ((bit >> i)%2 == 1) {
					if ((bit >> x[i][j]) % 2 != y[i][j]) {
						flag = false;
						//cout << "false1!";
						//cout << "i:" << i << " j:" << j << " bit:" << bit << " bitshift:" << ((bit >> x[i][j])%2) << " x[i][j]:" << x[i][j] <<  " y[i][j]:" << y[i][j] << endl;
						break;
					}
				}
				else {
					/*if ((bit >> x[i][j]) % 2 == y[i][j]) {
						flag = false;
						cout << "false2!";
						cout << "i:" << i << " j:" << j << " bit:" << bit << " bitshift:" << ((bit >> x[i][j])%2) << " x[i][j]:" << x[i][j] <<  " y[i][j]:" << y[i][j] <<  endl;
						break;
					}
					*/
				}
			}
			if (flag == false) break;
		}
		if (flag == false) continue;
		//cout << "bit:" << bit << endl;
		int temp = bit;
		int count = 0;
		while(temp > 0) {
			if(temp % 2 == 1) count++;
			temp /= 2;
		}
		max = max > count ? max : count;
	}

	cout << max << endl;

  return 0;
}


Measured memory_bytes: 256
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

H, W = map(int, input().split())
S = []
for i in range(H):
    S.append(input())

cell_name = [[np.infty]*W for i in range(H)]
count = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            cell_name[i][j] = count
            count += 1
            
tot_cell = count

dist = [[np.infty]*tot_cell for i in range(tot_cell)]

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            name = cell_name[i][j]
            if i >= 1:
                if S[i-1][j] == ".":
                    dist[name][cell_name[i-1][j]] = 1
            if i < H-1:
                if S[i+1][j] == ".":
                    dist[name][cell_name[i+1][j]] = 1
            if j >= 1:
                if S[i][j-1] == ".":
                    dist[name][cell_name[i][j-1]] = 1
            if j < W-1:
                if S[i][j+1] == ".":
                    dist[name][cell_name[i][j+1]] = 1

cost = floyd_warshall(dist)

max_dist = 0
for i in range(tot_cell):
    for j in range(tot_cell):
        if cost[i][j] > max_dist:
            max_dist = cost[i][j]
print(int(max_dist))

Measured memory_bytes: 18692
import sys
N, Y = [int(x) for x in input().split()]

y = Y//1000

for a in range((y-N)//9 + 1):
    if (y-N-9*a) % 4 == 0:
        b = (y-N-9*a)//4
        c = N - a - b
        if c >= 0:
            print('{0} {1} {2}'.format(a, b, c))
            sys.exit()

print('-1 -1 -1')

Measured memory_bytes: 3060
#include <stdio.h>
int main(void)
{
    int p[3],j1,j2,i,box1,box2;
    for(i=0;i<3;i++)
        scanf("%d",&p[i]);
    scanf("%d%d",&j1,&j2);
    if(p[0]<p[1]&&p[0]<p[2])
        box1=p[0];
    else if(p[0]<p[1]&&p[0]>p[2])
        box1=p[2];
    else if(p[0]>p[1]&&p[0]<p[2])
        box1=p[1];
    else
    {
        if(p[1]<p[2])
            box1=p[1];
        else
            box1=p[2];
    }
    if(j1<j2)
        box2=j1;
    else
        box2=j2;
    printf("%d\n",box1+box2-50);
    return 0;
}

Measured memory_bytes: 592
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<cstdio>
using namespace std;
int main(){
  string a,b;
  cin>>a>>b;
  if(a.length()>b.length())
    cout<<"GREATER"<<endl;
  else if(a.length()<b.length())
    cout<<"LESS"<<endl;
  else{
    //sort(a.begin(),a.end());
    //sort(b.begin(),b.end());
    //cout<<a<<endl<<b<<endl;
    for(int i=0;i<a.length();++i){
      if(a[i]==b[i])
        continue;
      else if(a[i]<b[i]){
        cout<<"LESS"<<endl;
        return 0;
      }
      else if(a[i]>b[i]){
        cout<<"GREATER"<<endl;
        return 0;
      }
    }
    cout<<"EQUAL"<<endl;
  }
}

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

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

    int N;
    cin >> N;
    vector<string> S(N);
    for (int i = 0; i < N; i++) {
        cin >> S[i];
        reverse(S[i].begin(), S[i].end());
    }
    sort(S.begin(), S.end(), [](auto& s1, auto& s2) {
        return s1.size() > s2.size();
    });
    map<ll, vector<int>> cnt;
    vector<int> one(26);
    ll ans = 0;
    for (auto& s : S) {
        int n = s.size();
        if (n == 1) {
            ans += one[s[0] - 'a'];
            continue;
        }
        vector<ll> hashes(n - 1);
        hashes[0] = s[0];
        for (int i = 1; i < n - 1; i++) hashes[i] = hashes[i-1] * 100007 + s[i];
        if (cnt.count(hashes[n-2])) ans += cnt[hashes[n-2]][s[n-1] - 'a'];
        vector<int> found(26);
        found[s[n-1] - 'a'] = 1;
        for (int i = n - 2; i > 0; i--) {
            found[s[i] - 'a'] = 1;
            if (cnt.count(hashes[i-1]) == 0) cnt[hashes[i-1]] = vector<int>(26);
            for (int c = 0; c < 26; c++) cnt[hashes[i-1]][c] += found[c];
        }
        found[s[0] - 'a'] = 1;
        for (int c = 0; c < 26; c++) one[c] += found[c];
    }
    cout << ans << endl;
}


Measured memory_bytes: 194000
import java.util.Scanner;

public class Main {
	Scanner sc = new Scanner(System.in);
	StringBuilder out;

	void run() {
		int N = sc.nextInt();
		int[] A = new int[N];
		for (int i = 0; i < A.length; i++) {
			A[i] = sc.nextInt();
		}

		int cnt = 0;
		for (int i = N - 1; i >= 0; i--) {
			for (int j = 0; j < i; j++) {
				if (A[j] > A[j + 1]) {
					int tmp = A[j];
					A[j] = A[j + 1];
					A[j + 1] = tmp;
					cnt++;
				}
			}
		}
		for (int i = 0; i < A.length; i++) {
			System.out.print((i == 0 ? "" : " ") + A[i]);
		}
		System.out.println("\n" + cnt);
	}

	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 19100
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF=1001001001;
vector<pair<int64_t,int64_t>>prime_factorize(int64_t x){
  vector<pair<int64_t,int64_t>>p;
  for(int64_t i=2;i*i<=x;i++){
    int cnt=0;
    if(x%i==0){
    while(x%i==0){cnt++;x/=i;}
    p.push_back(make_pair(i,cnt));
    }
  }
  if(x!=1){p.push_back(make_pair(x,1));}
  return p; 
}

int main() {
  int N,K;
  cin>>N>>K;
  string s;
  cin>>s;
  int cnt=0;
  for(int i=0;i<N-1;i++){
    if(s[i]==s[i+1]){cnt++;}
  }
  cout<<min(cnt+2*K,N-1)<<endl;
  return 0;
}

Measured memory_bytes: 3752
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  pair<int, int> p[2];
    for(int i=0; i<2; i++) cin >> p[i].first >> p[i].second;
    sort(p, p+2);
  int ans = min(p[0].second-p[1].first, p[1].second-p[1].first);
    (ans<0) ? ans=0 : ans;
    cout << ans << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pi M_PI
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1000000007,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;

void Main() {
  int c[5]={5,7,5,7,7};
  int n;
  while(R n && n) {
    vector<int> a(n);
    rep(i,n) {
      string s;
      R s;
      a[i]=s.size();
    }
    rep(i,n) {
      int x=i;
      rep(j,5) {
        int cnt=0;
        while(x<n&&cnt<c[j]) cnt+=a[x++];
        if(cnt!=c[j]) goto next;
      }
      pr(i+1);
      break;
    next:;
    }
  }
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 3212
using System;
using System.Collections.Generic;
using System.Linq;

public class Program
{
    public static void Main(string[] args)
    {
        var n = int.Parse(Console.ReadLine());
        var s = Console.ReadLine().ToCharArray();
        var cnt = 1;
        for (int i = 1; i < s.Length; i++)
        {
            if (s[i-1] != s[i])
            {
                cnt++;
            }
        }
        Console.WriteLine(cnt);
    }
}

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

using namespace std;

#define int long long

template <typename X, typename Y> void Max(X &x, Y y) {
  x = (x < y) ? y : x;
}
template <typename X, typename Y> void Min(X &x, Y y) {
  x = (x <= y) ? x : y;
}

const int N = 5005;
int n, a[N], f[N][N][2], h[N][2], sz[N];
vector <int> ad[N];

void dfs(int u, int p) {
  sz[u] = 1;
  f[u][0][0] = (a[u] < 0) ? 1e18 : a[u];
  f[u][0][1] = (a[u] > 0) ? 1e18 : a[u];
  for(auto &v : ad[u]) {
    if(v != p) {
      dfs(v, u);
      for(int i = 0; i < sz[u] + sz[v]; ++i) h[i][0] = h[i][1] = 1e18;
      for(int i = 0; i < sz[u]; ++i) {
        for(int j = 0; j < sz[v]; ++j) {
          int tot = i + j;
          Min(h[tot][0], f[u][i][0] + f[v][j][0]);
          Min(h[tot][1], f[u][i][0] + f[v][j][1]);
          Min(h[tot][1], f[u][i][1] + f[v][j][0]);
          Min(h[tot][1], f[u][i][1] + f[v][j][1]);
          if(f[v][j][0] < 1e18 || f[v][j][1] < 0) {
            Min(h[tot + 1][0], f[u][i][0]);
            Min(h[tot + 1][1], f[u][i][1]);
          }
        }
      }
      sz[u] += sz[v];
      for(int i = 0; i < sz[u]; ++i) {
        f[u][i][0] = h[i][0]; f[u][i][1] = h[i][1];
      }
    }
  }
}

main() {
  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  cin >> n;
  for(int i = 1; i <= n; ++i) cin >> a[i];
  for(int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    ad[u].push_back(v);
    ad[v].push_back(u);
  }
  dfs(1, -1);
  for(int i = 0; i < n; ++i) {
    if(f[1][i][0] < 1e18 || f[1][i][1] < 0) {
      cout << i;
      return 0;
    }
  }
}
/*
6
10 -1 10 -1 10 -1
1 2
2 3
3 4
4 5
5 6
*/


Measured memory_bytes: 391296
#include <bits/stdc++.h>
using namespace std;
#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++)
typedef int64_t llong;
char moji[26]={'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'};
char moji2[26]={'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'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define ld PRId64


int main(){
    string s;
    cin >> s;
    if(s[0] == s[2]) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

struct Node {
  int id;
  Node* parent = nullptr;
  Node* left = nullptr;
  Node* right = nullptr;
  int depth;
  int height;

  int calcHeight() {
    int leftHeight = left ? left->calcHeight() : -1;
    int rightHeight = right ? right->calcHeight() : -1;
    height = max(leftHeight, rightHeight) + 1;
    return height;
  }

  void calcDepth() {
    depth = parent ? parent->depth + 1 : 0;
    if (left) left->calcDepth();
    if (right) right->calcDepth();
  }

  int degree() {
    int d = 0;
    if (left) ++d;
    if (right) ++d;
    return d;
  }

  Node* sibling() {
    if (!parent) {
      return nullptr;
    }
    if (parent->left == this) {
      return parent->right;
    } else {
      return parent->left;
    }
  }
};

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

  int nodeCount;
  cin >> nodeCount;
  vector<Node> nodes(nodeCount);

  for (int i = 0; i < nodeCount; ++i) {
    int id, left, right;
    cin >> id >> left >> right;
    nodes[id].id = id;
    if (left >= 0) nodes[id].left = &nodes[left];
    if (right >= 0) nodes[id].right = &nodes[right];
    nodes[left].parent = &nodes[id];
    nodes[right].parent = &nodes[id];
  }
  Node* root = nullptr;
  for (int i = 0; i < nodeCount; ++i) {
    if (nodes[i].parent == nullptr) {
      root = &nodes[i];
      break;
    }
  }

  root->calcDepth();
  root->calcHeight();

  for (int i = 0; i < nodes.size(); ++i) {
    auto node = &nodes[i];
    auto parent = node->parent;
    auto sibling = node->sibling();
    auto type = (node == root) ? "root" : node->degree() ? "internal node" : "leaf";

    cout
      << "node " << i << ": "
      << "parent = " << (parent ? parent->id : -1) << ", "
      << "sibling = " << (sibling ? sibling->id : -1) << ", "
      << "degree = " << node->degree() << ", "
      << "depth = " << node->depth << ", "
      << "height = " << node->height << ", "
      << type << endl;
  }
}



Measured memory_bytes: 3196
#include <stdio.h>

int main(void)
{
  int x, y;

  while(1)
    {
      scanf("%d %d", &x, &y);

      if(x==0 && y==0)
        break;

      else if(y<x)
        printf("%d %d\n", y, x);

      else
        printf("%d %d\n", x, y);
    }
  return 0;
}

Measured memory_bytes: 596
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<functional>
#include<map>
#include<cstdlib>
#include<complex>
#include<numeric>
#include<set>

using namespace std;
using Int = long long;
Int INF = 1LL << 60;
const Int MOD = 1000000007;

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	Int n;
	cin >> n;

	vector<vector<Int>> even(100000 + 1, vector<Int>(2, 0));
	vector<vector<Int>> odd(100000 + 1, vector<Int>(2, 0));

	Int temp = 0;
	for (Int i = 0; i < 100001; i++) {
		even[i][1] = temp;
	    odd[i][1] = temp;
		temp++;
	}

	Int temp1 = 0;
	Int flag = 0;
	for (Int i = 0; i < n; i++) {
		cin >> temp;

		if (i == 0)temp1 = temp;
		if (temp1 != temp)flag = 1;


		if (i % 2)odd[temp][0]++;
		else if(i%2==0) even[temp][0]++;
		
	}

	sort(odd.begin(), odd.end(),greater<vector<Int>>());
	sort(even.begin(), even.end(),greater<vector<Int>>());

	Int ans = 0;
	if (flag == 0) {
		cout << n / 2 << endl;
		return 0;
	}

	if (odd[0][1] != even[0][1]) {
		ans = n - odd[0][0] - even[0][0];
		cout << ans << endl;
		return 0;
	}
	else {
		ans = min(n - odd[1][0] - even[0][0], n - odd[0][0] - even[1][0]);
		cout << ans << endl;
		return 0;

	}
}

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

bool canBuild(const string &s, const string &t) {
  for(int skip = 0; skip < (int)s.size(); ++skip) {
    for(int i = 0; i < (int)s.size(); ++i) {
      string x;
      for(int j = i; j < (int)s.size() && x.size() < t.size(); j += skip + 1) {
        x.push_back(s[j]);
      }
      if(x == t) return true;
    }
  }
  return false;
}

int main() {
  int N; cin >> N;
  string T; cin >> T;
  int ans = 0;
  while(N--) {
    string S; cin >> S;
    if(canBuild(S, T)) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 1212
use std::io::*;

fn main() {
    let mut s: String = String::new();
    std::io::stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();
    let k: usize = itr.next().unwrap().parse().unwrap();
    let a: usize = itr.next().unwrap().parse().unwrap();
    let b: usize = itr.next().unwrap().parse().unwrap();

    for i in a..b + 1 {
        if i % k == 0 {
            println!("OK",);
            return;
        }
    }
    println!("NG",);
}


Measured memory_bytes: 2108
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001001001001
#define mod 1000000007
#define mod2 998244353
#define pi acos(-1)
#define all(v) v.begin(),v.end()

ll gcd(ll a,ll b){
    if(b>a) swap(a,b);
    if(b==0) return a;
    return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    ll g=gcd(a,b);
    return a/g*b;
}
ll rep_jijo(ll n,ll x){
    if(x==0) return 1;
    if(x%2==0){
        ll t=rep_jijo(n,x/2);
        return t*t;
    }
    return n*rep_jijo(n,x-1);
}

int main(){
    vector<int>n(5);
    int ans;
    rep(i,5){
        int x;
        cin >> x;
        if(x==0){
            ans = i+1;
        }
    }
    cout << ans <<endl;
   return 0;
}

Measured memory_bytes: 3620
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
	using namespace std;
struct data
{
	int a;
	int b;
}s[100005];
bool cmp(data x,data y)
{
	return x.a<y.a;
}
int main()
{
	int n=0,m=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%d%d",&s[i].a,&s[i].b);
	sort(s+1,s+m+1,cmp);
	int w=s[1].b,ans=0;
	for(int i=1;i<m;i++)
		if(s[i+1].a<w) w=min(w,s[i+1].b);
				  else ans++,w=s[i+1].b;
	printf("%d",ans+1);
	return 0;
}

Measured memory_bytes: 1024