akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <cstdio>
#include <cstring>
#define w(i, j) (c[j] - c[(i)-1])

typedef long long L;
const int N = 6e2 + 26, P = 1e9 + 7;

struct mod_t {
	static int norm(int x) { return x + (x >> 31 & P); }
	static void norm2(int& x) { x += x >> 31 & P; }
	int x;
	mod_t() {}
	mod_t(int v) : x(v) {}
	mod_t(long long v) : x(v) {}
	mod_t(char v) : x(v) {}
	mod_t operator+(const mod_t& rhs) const { return norm(x + rhs.x - P); }
	mod_t operator-(const mod_t& rhs) const { return norm(x - rhs.x); }
	mod_t operator*(const mod_t& rhs) const { return (L)x * rhs.x % P; }
	void operator+=(const mod_t& rhs) { norm2(x += rhs.x - P); }
	void operator-=(const mod_t& rhs) { norm2(x -= rhs.x); }
	void operator*=(const mod_t& rhs) { x = (L)x * rhs.x % P; }
};

mod_t f[N][N], g[N], ans;
int p[N], c[N];
int n, k;
int h(int l, int r) { return (r - l + 1) - w(l, r); }
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1, x, y; i <= k; i++) {
		scanf("%d%d", &x, &y);
		x[p] = y, y[p] = x, x[c] = y[c] = 1;
	}

	g[0] = g[1] = 1;
	for (int i = 2; i <= 2 * n; i++) g[i] = g[i - 2] * (i - 1);
	for (int i = 1; i <= 2 * n; i++) c[i] += c[i - 1];

	for (int l = 1; l <= 2 * n; l++)
		for (int r = l + 1; r <= 2 * n; r++)
			if ((l ^ r) & 1) {
				for (int x = l; x <= r; x++)
					if (x[p] && (x[p] < l || x[p] > r)) goto end;
				f[l][r] = g[h(l, r)];
				for (int x = l + 1; x < r; x++) f[l][r] -= f[l][x] * g[h(x + 1, r)];
				ans += f[l][r] * g[(n << 1) - (r - l + 1) - ((k << 1) - w(l, r))];
			end:;
			}
	printf("%d", ans.x);
}

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

// 総数を1000000007で割った余り
const long long mod = 1e9 + 7;

using ll  = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define rep1r(i, n) for (int i = ((int)(n)); i > 0; --i)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

static const int MAXN = 500000;
#define SENTINEL 2000000000
int L[MAXN / 2 + 5], R[MAXN / 2 + 5];
int a[MAXN + 5];
int cnt, n;

void merge(int a[], int n, int left, int mid, int right) {
    int n1          = mid - left;
    int n2          = right - mid;
    rep(i, n1) L[i] = a[left + i];
    rep(i, n2) R[i] = a[mid + i];
    L[n1] = R[n2] = SENTINEL;
    int i = 0, j = 0;
    for (int k = left; k < right; k++) {
        cnt++;
        if (L[i] <= R[j]) {
            a[k] = L[i++];
        } else {
            a[k] = R[j++];
        }
    }
}

void mergeSort(int a[], int n, int left, int right) {
    if (left + 1 < right) {
        int mid = (left + right) / 2;
        mergeSort(a, n, left, mid);
        mergeSort(a, n, mid, right);
        merge(a, n, left, mid, right);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // cout << fixed << setprecision(5);

    cin >> n;
    rep(i, n) { cin >> a[i]; }
    mergeSort(a, n, 0, n);
    rep(i, n) {
        if (i) cout << " ";
        cout << a[i];
    }
    cout << endl;
    cout << cnt << endl;

    return 0;
}



Measured memory_bytes: 6928
// includes {{{
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<random>
#include<cassert>
#include<bitset>
#include<cstdlib>
// #include<deque>
// #include<multiset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;

bool a[9 * 9 + 1];
int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  for(int i = 1; i <= 9; i++) 
  for(int j = 1; j <= 9; j++) a[i*j] = 1;
  int n;
  cin >> n;
  cout << (a[n] ? "Yes" : "No") << endl;
  return 0;
}


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

using ll=long long;
const ll MOD=1e9+7;
int main(){
    int n;
    cin>>n;
    vector<char> c(n);
    for(int i=0;i<n;i++) cin>>c[i];
    vector<vector<ll>> dp(n+1,vector<ll>(n+1,0));
    dp[0][0]=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(c[i]=='-'){
                dp[i+1][j]=dp[i][j];
            }
            if(c[i]=='U'){
                (dp[i+1][j+1]+=dp[i][j])%=MOD;
                (dp[i+1][j]+=dp[i][j]*j)%=MOD;
            }
            if(c[i]=='D'){
                if(j-1>=0){
                    (dp[i+1][j]+=dp[i][j]*j)%=MOD;
                    (dp[i+1][j-1]+=(dp[i][j]*j)%MOD*j)%=MOD;
                }
            }
        }
    }
    cout<<dp[n][0]<<endl;
    return 0;
}


Measured memory_bytes: 3276
def solve(data, x, y)
  range = -3..3
  if data[y][x] == 1
    data[y][x] = 0
    #横に走査
    range.each do |r|
      next if x + r < 0 || x + r > 7
      if data[y][x + r] == 1
        data = solve(data, x + r, y)
      end
    end
    #縦に走査
    range.each do |r|
      next if y + r < 0 || y + r > 7
      if data[y + r][x] == 1
        data = solve(data, x, y + r)
      end
    end
  end
  data
end

def print(data)
  l = data.size
  l.times do |i|
    l.times do |j|
      printf "%d", data[i][j]
    end
    printf "\n"
  end
end

($stdin.gets.to_i).times do |t|
  $stdin.gets
  data = Array.new
  8.times do |i|
    data << $stdin.gets.chomp.split("").map(&:to_i)
  end

  x =$stdin.gets.to_i - 1
  y =$stdin.gets.to_i - 1
  printf "Data %d:\n", t + 1
  print(solve(data, x, y))
end

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

using namespace std;
using ll = long long;

ll q[(ll)(1e5)+2];

int main(void){
    ll N, K;
    cin >> N >> K;
    for(ll i=0;i<N;i++){
        ll a, b;
        cin >> a >> b;
        q[a] += b;
    }
    ll ans = 0;
    ll k = 0;
    for(ll i=0;i<sizeof(q)/sizeof(ll);i++){
        k += q[i];
        ans = i;
        if(k >= K) break;        
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
int main(void)
{
  int n;
  int sum=0;
  scanf("%d",&n);
  while(n-->0){
    int l,r;
    scanf("%d %d",&l,&r);
    sum+=r-l+1;
  }
  printf("%d\n",sum);
  return 0;
}


Measured memory_bytes: 128
#include "bits/stdc++.h"
// Custom Header {{{
#define ALL(x) x.begin(), x.end()
#define rep(i, s, n)      for(int i(s); i < int(n); ++i)
#define endl '\n'
#ifndef YDK
#define eprintf(...)
#endif
using namespace std;
using i64 = long long;
using pii = pair<i64, i64>;
template<class A, class B>inline bool chmax(A &a, const B &b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b<a ? a=b,1 : 0;}
constexpr const int INF  = 0x3f3f3f3f;
constexpr const i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr const int MOD  = int(1e9) + 7;
// }}}

// Library {{{

// }}}


signed main()
{
    i64 X, Y;
    cin >> X >> Y;

    int ans = 1;
    i64 val = X;
    while (true) {
        val <<= 1;
        if (val > Y) break;
        ++ans;
    }

    cout << (ans) << endl;
    return 0;
}


Measured memory_bytes: 256
// #define DEBUGGING
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()

template <typename T> using V = vector<T>;
template <typename T> using VV = V<V<T>>;
using ll = int64_t;
using ull = uint64_t;
using PLL = pair<ll, ll>;

template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return min(t, var_min(tail...)); }
template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return max(t, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
template <typename T> const T& clamp(const T &t, const T &low, const T &high) { return max(low, min(high, t)); }
template <typename T> void chclamp(T &t, const T &low, const T &high) { t = clamp(t, low, high); }

namespace init__ {

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

}

#ifdef DEBUGGING
// #include "../debug/debug.cpp"
#include "../../debug/debug.cpp"
#else
#define DEBUG(...) 0
#define DEBUG_SEPARATOR_LINE 0
#endif

template <typename T>
T make_v(T init) { return init; }

template <typename T, typename... Tail>
auto make_v(T init, size_t s, Tail... tail) {
#define rec make_v(init, tail...)
    return V<decltype(rec)>(s, rec);
#undef rec
}

int main() {
    ll N;
    cin >> N;
    V<ll> A(N);
    for(auto &&ele : A) cin >> ele;
    auto ite = max_element(ALL(A));
    ll rest = 0;
    for(ll i = 0; i < N; i++) {
        if(distance(A.begin(), ite) == i) continue;
        chmax(rest, A[i]);
    }
    for(ll i = 0; i < N; i++) {
        if(distance(A.begin(), ite) != i) cout << *ite;
        else cout << rest;
        cout << endl;
    }
    return 0;
}


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

using namespace std;
#define all(a)a.begin(),a.end()
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod = int(1e9)+7;
using V = vector<int>;
using P = pair<int,int>;

int main()
{
    ll n,m;cin >>n>>m;
    V h(n);
    rep(i,n)cin >>h[i];
    vector<V> g(n);
    rep(i,m){
        ll a,b;cin >>a>>b;
        a--;b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<bool>c(n,true);
    rep(i,n){
        for(ll u:g[i]){
            if(h[i]<=h[u])c[i]=false;
            if(h[i]>=h[u])c[u]=false;
        }
    }
    ll ans=0;
    rep(i,n)if(c[i])ans++;
    cout << ans << endl;
    return 0;
}


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

const int MAX = 1e6 + 1;
int cnt[MAX];
int ans[MAX];

signed main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    int max = 0;

    for (int _ = 0; _ < n; _++) {
        int i;
        std::cin >> i;
        ++cnt[i];
        max = std::max(max, i);
    }

    for (int i = 1; i <= max; i++) {
        for (int j = i; j <= max; j += i) {
            ans[i] += cnt[j];
        }
    }

    for (int i = 2; i <= max; i++) {
        if (ans[i] == n) {
            std::cout << "not coprime";
            return 0;
        }
    }

    for (int i = 2; i <= max; i++) {
        if (ans[i] > 1) {
            std::cout << "setwise coprime";
            return 0;
        }
    }

    std::cout << "pairwise coprime";

    return 0;
}



Measured memory_bytes: 11460
N = int(input())
W = list(map(int, input().split()))
min = 100000
min_n = 0
for i in range(N):
    s1 = sum(W[:i])
    s2 = sum(W[i:])

    if min > abs(s1 -s2):
        min = abs(s1-s2)

print(min)


Measured memory_bytes: 2940
k,n = map(int,input().split())	
li = list(map(int,input().split()))
big = 0
for i in range(n-1):
  d = li[i+1] - li [i]
  big = max(d,big)
dd = (k - li[-1]) + li[0]
big = max(big,dd)
print(k - big)

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

int main() {
  int N,A;
    cin >> N >> A;
  int M = N % 500;
  
  //cout << M << endl;
  
  if (M <= A) {
    cout << "Yes" << endl;
  }
  else{
  cout << "No" << endl;
  }    
}

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

#define rep(i,n) for(int i = 0; i < n; i++)
#define REP(i,n) for(int i = 1; i < n; i++)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using vs = vector<string>;
using vb = vector<bool>;
using vc = vector<char>;
using vcc = vector<vc>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
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(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, t;
  cin >> n >> t;
  vi time(n);
  rep(i,n) cin >> time[i];
  ll ans = 0;
  REP(i,n) {
    ans += min(t, time[i]-time[i-1]);
  }
  ans += t;
  cout << ans << endl;
}

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

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> vta(n);
    for (int i = 0; i < n; ++i) {
        cin >> vta[i];

    }

    int m;
    cin >> m;
    vector<int> vtb(m);
    for (int i = 0; i < m; ++i) {
        cin >> vtb[i];
    }

    vector<int> res;
    set_intersection(vta.begin(), vta.end(), vtb.begin(), vtb.end(),
                     back_inserter(res));

    for (auto x:res) cout << x << endl;
    return 0;
}


Measured memory_bytes: 4828
import java.util.Scanner;

public class Main extends Exception{
    public static void main(String[] args) {
        Scanner s1 = new Scanner(System.in);
        int a=s1.nextInt();
        int b=s1.nextInt();

        a=a*b;
        if (a%2==0){
            System.out.println("Even");
        }else {
            System.out.println("Odd");
        }
    }
}


Measured memory_bytes: 23764
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n; cin >> n;
  vector<int> nums(n);
  for (int i = 0; i < n; i++) cin >> nums[i];
  for (int i = n - 1; i >= 0; i--){
    cout << nums[i];
    if (i != 0) cout << " ";
    else cout << endl;
  }
}


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

double expectation(double num, double num_mem);

int main(){

    int N, K;
    cin >> N >> K;

    vector<double> E(N);
    int temp;

    for (int i=0; i<N; i++){
        cin >> temp;
        E.at(i) = expectation(temp, temp);
    }
    /*
    for (int i=0; i<N; i++){
        cout << E.at(i) << " ";
    }
    cout << endl;
    */

    vector<double> E_sum(N);
    E_sum.at(0) = E.at(0);
    for (int i=1; i<N; i++){
        E_sum.at(i) = E.at(i) + E_sum.at(i-1);
    }
    /*
    for (int i=0; i<N; i++){
        cout << E_sum.at(i) << " ";
    }
    cout << endl;
    */

    double sum = 0;
    double E_max = 0;
    for (int i=0; i<(N-K+1); i++){
        if (i == 0){
            sum = E_sum.at(i+K-1);
        }
        else{
            sum = E_sum.at(i+K-1) - E_sum.at(i-1);    
        }

        if (E_max < sum){
            E_max = sum;
        }
    }

    cout << fixed << setprecision(15);
    cout << E_max << endl;
    return 0;
}

double expectation(double num, double num_mem){

    if (num == 1){
        return 1.0/num_mem;
    }
    else{
        return (num/num_mem) + expectation(num-1.0, num_mem);
    }
}

Measured memory_bytes: 3456
while 1:
    N,M = map(int,raw_input().split())
    if N == M == 0: break
    DP = [map(int,raw_input().split()) for _ in xrange(N)]
    DP = sorted(DP, key = lambda x:x[1])[::-1]
    ans = 0
    for i in xrange(N):
        ans += DP[i][1]*max(0,DP[i][0]-M)
        M = max(0,M-DP[i][0])
    print ans

Measured memory_bytes: 5904
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(t) t.begin(), t.end()
#define inrange(i, a, b) (((i)>= min((a), (b))) && ((i) <= max((a), (b))))
typedef vector<ll> vi;
#define fi first
#define se second
const ll inf = 9e18;
const ll mod = 1e9 + 7;

void print(ll a[], ll n){for(ll i=0;i<n;i++){cout<<a[i]<<" ";}cout<<"\n";}
ll power(ll x, ll y, ll M = inf){
    ll ans = 1;
    x %= M;
    while(y){
        if(y&1)
            ans = (x * ans) % M;

        x = (x * x) % M;
        y >>= 1;
    }
    return ans;
}
ll modInverse(ll n) {return power(n, mod-2, mod);}
inline ll mul(ll a, ll b){ return (a * b) % mod; }
inline ll sub(ll a, ll b){ ll c = a - b; if(c < 0) c += mod; return c; }
inline ll add(ll a, ll b){ ll c = a + b; if(c > mod) c -= mod; return c; }
inline ll divi(ll a, ll b){ return mul(a, modInverse(b)); }

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

	string s;
	cin>>s;
	if(s[0] == s[1] && s[1] == s[2])
		cout<<"No\n";
	else {
		cout<<"Yes\n";
	}
return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
bool judge(int x,vector<int> d){
  int siz = d.size();
  while(x != 0){
    int n = x % 10;
    for(int i = 0;i < siz;i++){
      if(n == d[i])return false;
    }
    x /= 10;
  }
  return true;
}

int main(){
  int n,k;
  cin >> n >> k;
  vector<int> d(k);
  for(int i = 0;i < k;i++)cin >> d[i];
  for(int i = n;;i++){
    if(judge(i,d)){
      cout << i << endl;
      break;
    }
  }
}

Measured memory_bytes: 256
function Main(input) {

    tmp = input.split("");
    var a = tmp[0];
    var b = tmp[1];
  　var c = tmp[2];
	if(a === b && b===c){
       console.log('No');
    }else{
      console.log('Yes');
    }
   
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 21064
#include <stdio.h>

int main()
{
	int h = 1, w = 1, i, j;
	while(1)
	{
		scanf("%d %d", &h, &w);
		if(h == 0 && w == 0)
			break;
		for(j = 1; j <= h; j++)
		{
			for(i = 1; i <= w; i++)
			{
				if((j%2==1&&i%2==1)||(j%2==0&&i%2==0))
				printf("#");
				else
				printf(".");
			}
			printf("\n");
		}
		printf("\n"); 
	}
	return 0;
}


Measured memory_bytes: 2600
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 2e5 + 5;
struct node
{
	int x, y, px, py;
}p[N];
bool cmp(node a, node b)
{
	return a.px < b.px;
}
bool dmp(node a, node b)
{
	return a.py < b.py;
}
int n, maxn = 0;
int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++)
	{
		scanf("%d%d", &p[i].x, &p[i].y);
		p[i].px = p[i].x + p[i].y;
		p[i].py = p[i].y - p[i].x;
	}
	sort(p + 1, p + n + 1, cmp);
	maxn = p[n].px - p[1].px;
	sort(p + 1, p + n + 1, dmp);
	maxn = max(maxn, p[n].py - p[1].py);
	printf("%d", maxn); 
	return 0;
} 

Measured memory_bytes: 6932
n, m, l = map(int, input().split())
A = [list(map(int, input().split())) for i in range(n)]
B = [list(map(int, input().split())) for i in range(m)]
C = [[0 for i in range(l)] for j in range(n)]
for i in range(n):
    for j in range(l):
        for k in range(m):
            C[i][j] += A[i][k]*B[k][j]
for i in range(n):
    print(" ".join(map(str, C[i])))


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

using namespace std;

#define ll long long 
#define Fastest ios_base :: sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl "\n"

int main()
{
	int n,a;
	
	cin >> n;
	
	double sum = 0;
	
	for(int i = 1; i <= n; i++)
	{
		cin >> a;
		sum += (1/(a*1.0));
	}
	
	double ans = (1/(sum*1.0));
	cout <<setprecision(5)<<fixed<< ans << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include<algorithm>
#include<cassert>
#include<cmath>
#include<cstdio>
#include<iostream>
#include<numeric>
#include<string>
#include<deque>
#include<vector>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const ll mod = 1e9+7;
const double PI = acos(-1);  // PI = 3.141593...

struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

struct combination {
    vector<mint> fact, ifact;
    combination(int n):fact(n+1),ifact(n+1) {
        assert(n < mod);
        fact[0] = 1;
        for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
        ifact[n] = fact[n].inv();
        for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
    }
    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fact[n]*ifact[k]*ifact[n-k];
    }
};

int main() {
    int n, k;
    cin >> n >> k;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    sort(a.begin(), a.end());
    vector<mint> v(n);
    rep(i, n) v[i] = a[i];

    combination comb(n);
    mint ans = 0;
    // max
    for(int i=k; i<=n; ++i) {
        ans += v[i-1] * comb(i-1, k-1);
    }
    // min
    for(int i=0; i<=n-k; ++i) {
        ans -= v[i] * comb(n-i-1, k-1);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3328
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
using namespace std;
#define sz(a) ((int) (a).size())

int main() {
	string target = "keyence", s;
	cin >> s;
	for (int i = 0; i < sz(s); ++i) {
		for (int j = i; j <= sz(s); ++j) {
			string t = s;
			t.erase(t.begin() + i, t.begin() + j);
			if (t == target) {
				printf("YES\n");
				return 0;
			}
		}
	}
	printf("NO\n");
	return 0;
}

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

typedef long long LL;

const int N=300;

int n,m,sk;
char s[N+9][N+9];

void into(){
  scanf("%d%d%d",&n,&m,&sk);
  for (int i=1;i<=n;++i)
	scanf("%s",s[i]+1);
}

int ans[N+9][N+9];

void Get_ans(){
  int now=0;
  for (int i=1;i<=n;++i){
	int flag=0;
	for (int j=1;j<=m;++j){
	  if (s[i][j]=='#') ++now,flag=1;
	  ans[i][j]=now+!flag;
	}
	if (!flag)
	  for (int j=1;j<=m;++j) ans[i][j]=ans[i-1][j];
  }
  for (int i=n;i>=1;--i)
	for (int j=1;j<=m;++j)
	  if (!ans[i][j]) ans[i][j]=ans[i+1][j];
}

void work(){
  Get_ans();
}

void outo(){
  for (int i=1;i<=n;++i){
	for (int j=1;j<=m;++j)
	  printf("%d ",ans[i][j]);
	puts("");
  }
}

int main(){
  into();
  work();
  outo();
  return 0;
}

Measured memory_bytes: 4228
#include <bits/stdc++.h>
#ifdef LOCAL_DEBUG
#define DEBUG 1
#define CERR if(DEBUG) cerr
#define MACRO(_1,_2,_3,_4,_5,_6,_7,_8,_9,_10,NAME,...) NAME
#define pr(...) CERR<<MACRO(__VA_ARGS__,pr10,pr9,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__)<<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
#define pr9(a,b,c,d,e,f,g,h,i) pr1(a)<<pr8(b,c,d,e,f,g,h,i)
#define pr10(a,b,c,d,e,f,g,h,i,j) pr1(a)<<pr9(b,c,d,e,f,g,h,i,j)
#define prArr(a){CERR<<(#a)<<"={";int i=0;for(auto t:(a))CERR<<(i++?", ":"")<<t;CERR<<"}"<<endl;}
#else
#define DEBUG 0
#define pr(...)
#define prArr(a)
#endif
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<60)+1e9; // ~ 1.15 * 1e18
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}
//INSERT ABOVE HERE


signed main(){
  srand((unsigned)time(NULL));
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  Int N, K;
  cin>>N>>K;

  multiset<P> topK;
  vector<P> mx(N, P(-1, -1));
  for(Int i=0;i<N;i++){
    Int t, d;
    cin>>t>>d; t--;
    topK.insert(P(d, t));
    Max(mx[t], P(d, t));
  }

  multiset<P> other;
  while((Int)topK.size() != K){
    Int t, d; tie(t, d) = *topK.begin();
    topK.erase(topK.begin());
    other.insert(P(d, t));
  }
  Int sum = 0;
  for(auto p:topK) sum += p.first;
  sort(mx.begin(), mx.end(), greater<P>());

  Int ans = sum;
  for(Int i=1;i<=K;i++){
    auto p = mx[i-1];
    if(p == P(-1, -1)) break;
    Int d, t; tie(d, t) = p;
    auto it = topK.find(P(d, t));
    if(it != topK.end()) topK.erase(it);
    else {
      sum -= topK.begin()->first;
      sum += d;
      topK.erase(topK.begin());
    }
    Int score = i * i + sum;
    Max(ans, score);
  }

  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 8064
import java.util.Scanner;

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

		int A = sc.nextInt();
		int B = sc.nextInt();
		int T = sc.nextInt();

		int counter = (T / A)* B;




System.out.print(counter);

	}


}

Measured memory_bytes: 23124
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
#define INF (1<<30)
#define LINF (1LL<<60)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
typedef unsigned long long int ull;
typedef long long lint;

set<int> oddedge[100000],evenedge[100000];
bool color[100000]={};

void DFS(int x,int depth){
  color[x]=depth%2;
  while(!oddedge[x].empty()){
    int y=*oddedge[x].begin();
    oddedge[x].erase(y);
    oddedge[y].erase(x);
    DFS(y,depth+1);
  }
  while(!evenedge[x].empty()){
    int y=*evenedge[x].begin();
    evenedge[x].erase(y);
    evenedge[y].erase(x);
    DFS(y,depth);
  }

}
int main(void){
  int N;
  cin >> N;
  rep(i,N-1){
    int x,y,z;
    cin >> x >> y >> z;
    x--,y--;
    if(z%2==0){
      evenedge[x].insert(y);
      evenedge[y].insert(x);
    }
    else{
      oddedge[x].insert(y);
      oddedge[y].insert(x);
    }
  }
    DFS(0,0);
    rep(i,N) cout << color[i] << endl;
}

Measured memory_bytes: 22144
//  Created by conan1024hao in 2019.
//  Copyright © 2019 conan1024hao. All rights reserved.
//  専用ライブラリです、自由にコピーして構いません。
//  感谢看我的代码！Wechat:conan1024hao QQ:810396815
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define INF 10e16
#define MOD 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
//using Int=int_fast64_t;
typedef long long int ll;
typedef pair<ll,ll>Pll;
typedef pair<int,int>Pin;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[8]={-1,0,1,0,1,1,-1,-1};
int dy[8]={0,-1,0,1,1,-1,1,-1};
char dir[4]={'u','l','d','r'};
ll cmp1(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}
//--------------------------------------------------------------------------

//---------------------------------------------------------------------------
int main(){//問題をちゃんと見ろ!!!!!!!!!!!!!!!!!      llか??????????        memset()!!!!!!!!!!!!
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, K, A[101], dp[101010];
    //---------------------------------------------------------------------------------------------------
        cin >> N >> K;
        rep(i, 0, N) cin >> A[i];
     
        rep(k, 0, K + 1) {
            int lose = 0, cnt = 0;
            rep(i, 0, N) if (0 <= k - A[i]) {
                cnt++;
                if(!dp[k - A[i]]) lose++;
            }
            if (cnt == 0) dp[k] = 0;
            else if (0 < lose) dp[k] = 1;
            else dp[k] = 0;
        }
     
        if (dp[K]) printf("First\n");
        else printf("Second\n");
   
    
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------


Measured memory_bytes: 640
#include <stdio.h>
#define N 250
 
int Parent(int);
int LeftC(int);
int RightC(int);
 
int main(){
  int n,i;
  int num[N];
 
  scanf("%d",&n);
  for(i=1;i<=n;i++){
    scanf("%d",&num[i]);
  }
  for(i=1;i<=n;i++){
    printf("node %d: key = %d, ",i,num[i]);
    if(Parent(i)>=1) printf("parent key = %d, ",num[Parent(i)]);
    if(n>=LeftC(i)) printf("left key = %d, ",num[LeftC(i)]);
    if(n>=RightC(i)) printf("right key = %d, ",num[RightC(i)]);
    printf("\n");
  }
  return 0;
}
 
int Parent(int i){
  return i/2;
}
 
int LeftC(int i){
  return 2*i;
}
 
int RightC(int i){
  return 2*i+1;
}

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

int main() {

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

  if (a == b) {
    cout << "a == b"<< endl;
  }
  else if (a > b) {
    cout << "a > b"<< endl;
  }
  else if (a < b) {
    cout << "a < b"<< endl;
  }

  return  0;
}



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

using namespace std;

int main(){
    int n;
    cin>> n;
    n%=10;
    if( n == 2 || n == 4 || n == 5 || n == 7 || n == 9){
        cout << "hon";
    }
    else if( n == 3){
        cout << "bon";
    }
    else{
        cout << "pon";
    }
}


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

int kaibun(int n){
  int s = 0;
  int S;
  vector<int> a(5),b(5);
  int i=4;
  while(i>=0){
    a.at(i) = n%10;
    n /= 10;
    i--;
  }
  for(int j=0;j<5;j++){
    b.at(j) = a.at(4-j);
    if(b.at(j) == a.at(j)) s++;
  }
  if(s == 5) S = 1;
  else S = 0;
  
  return S;
}

int main() {
  int a,b,ans,s;
  cin >> a >> b;
  ans = 0;
  for(int i=a;i<=b;i++){
    s = kaibun(i);
    ans += s;
  }
  
  cout << ans << endl;
  
  return 0;
}


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

using ll = long long;
#define ld long double
#define ull unsigned long long int

#define rep(i, n) for (int i = 0; i < (int)(n); i++)  // (i, 10) i=0～i=9まで
#define repr(i, n) for (int i = n; i >= 0; i--)   // (i, 10) i=10～i=0まで
#define FOR(i, m, n) for (int i = m; i < n; i++)  // (i, 3, 10) i=3～i=9まで
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pb push_back
#define ret return

typedef pair<int, int>    pii;
typedef vector<int>       vi;
typedef vector<vi>        vii;
typedef vector<long long> vl;

// 総数を1000000007で割った余り
const long long mod = 1e9 + 7;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
    // cin.tie(0);
    // ios::sync_with_stdio(false);
    // cout << fixed << setprecision(5);

    // 入力
    int a, b, c;
    cin >> a >> b >> c;

    // 処理
    cout << a * b / 2 << endl;

    // 出力

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define long long long
using namespace std;
map<string,int>mp;
int main()
{
  ios_base::sync_with_stdio(0);cin.tie(0);
  int n;cin>>n;string s="#",k;
  while(n--)
  {
    cin>>k;
    if(mp[k])cout<<"No"<<endl,exit(0);
    mp[k]=1;
    if(s=="#")
    {
      s=k;
      continue;
    }
    if(k[0]!=s.back())cout<<"No"<<endl,exit(0);
    s=k;
  }
  if(mp[k])cout<<"Yes"<<endl,exit(0);
  return 0;
}


Measured memory_bytes: 384
#include<stdio.h>
int main(void)
{
  int m, plan, set, money, year, part, total, top, answer[500]={0}; 
  double r;
  scanf("%d", &m);
  int i, j, k;

  for(i=0; i<m; i++)
    {
      scanf(" %d %d %d", &money ,&year, &part);
      for(j=0; j<part; j++)
	{
/*	  scanf(" %d %f %d", &plan, &r, &set);*/
	  scanf(" %d %lf %d", &plan, &r, &set);
	  total=money;
	  if(plan==0)  //??????
	    {
	      top=0;
	      for(k=0; k<year; k++)
		{
		  top+=total*r;
		  total-=set;
		}
	      total+=top; 
	      if(answer[i]<=total)
		{
		  answer[i]=total; //?????§???   
		}   
	    }
	  else if(plan==1)//??????
	    {
	      for(k=0; k<year; k++)
		{
		  total+=total*r-set;	  
		}
	      if(answer[i]<=total)
		{
		  answer[i]=total; //?????§???   
		}
	    }
	  else
	    {
	      break;
	    }
	}
    }
  for(i=0; i<m; i++) printf("%d\n", answer[i]);

  return 0;
}

Measured memory_bytes: 632
#include"bits/stdc++.h"
#include<valarray>

using namespace std;

#define MAX 200002

int n;
int x;

char buf[MAX];
string s;
string t;

vector<pair<int,long long int> > v;

#define MOD 998244353

long long int p2[MAX];


int main(){
	cin>>n;
	scanf("%s",buf);
	s=buf;
	for(int i=0;i<n;i++){
		//cout<<s<<endl;
		s.push_back('1'-s[i]+'0');
	}
	//cout<<s<<endl;
	t=s;
	p2[0]=1;
	for(int i=1;i<MAX;i++){
		p2[i]=p2[i-1]*2;
		p2[i]%=MOD;
	}
	for(int i=1;i<=2*n;i++){
		if(2*n%i)continue;
		int num=(2*n)/i;
		if(num%2==0)continue;
		int len=i/2;
		long long int ans=0;
		for(int j=0;j<len;j++){
			if(s[j]=='1'){
				ans+=p2[len-j-1];
			//	cout<<len<<" "<<ans<<" "<<p2[len-j-1]<<endl;
				if(ans>=MOD)ans%=MOD;
			}
		}
		for(int j=0;j<2*n;j++){
			int rep=j/len;
			rep%=2;
			int att=j%len;
			if(rep==0){
				t[j]=s[att];
			}
			else{
				t[j]='1'-s[att]+'0';
			}
		}
	//	cout<<s<<" "<<t<<endl;
		if(s>=t){
			ans++;
		}
		if(ans>=MOD)ans%=MOD;
		v.push_back(make_pair(len,ans));
		//cout<<len<<" "<<ans<<endl;
	}
	long long int ans=0;
	for(int i=0;i<v.size();i++){
		for(int j=i+1;j<v.size();j++){
			if(v[j].first%v[i].first==0LL){
				v[j].second+=MOD-v[i].second;
				v[j].second%=MOD;
			}
		}
		ans+=v[i].first*(long long int)v[i].second;
		ans%=MOD;
	}
	ans*=2LL;
	ans%=MOD;
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 2748
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {

        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };


    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        s: String,
    }
    let nums: Vec<i32> = s.chars().map(|c| c.to_digit(10).unwrap() as i32).collect();
    for d in 0..1 << 3 {
        let mut sum = nums[0];
        for i in 0..3 {
            if ((d & (1 << i)) as u8).trailing_zeros() == i {
                sum += nums[(i + 1) as usize];
            } else {
                sum -= nums[(i + 1) as usize];
            }
        }
        if sum == 7 {
            let mut ans = "".to_string();
            ans += &nums[0].to_string();
            for i in 0..3 {
                if ((d & (1 << i)) as u8).trailing_zeros() == i {
                    ans += "+";
                } else {
                    ans += "-";
                }
                ans += &nums[(i + 1) as usize].to_string();
            }
            ans += "=7";
            println!("{}", ans);
            return;
        }
    }
}


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

#define Max(a,b) max({a,b})
#define Min(a,b) min({a,b})
#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rep1(i,n) for(long long int (i)=1;(i)<(int)(n);(i)++)
#define len(n) n.size()
#define print(n) cout << n << endl;

// s.substr(i,n)

using namespace std;

//char a = 65;

int n,m,a,b,c,cou,co;
double d,k;
char num = 65;
string s,t;


int main(){
    
    cin >> s;
    n = len(s);

    string ans = "AC";
    if(s[0] != 'A'){
        ans = "WA";
    }

    cou = 0;

    rep1(i,n){
        if(isupper(s[i])){
            if(i == 1 || i == n-1 || s[i] != 'C'){
                ans = "WA";
            }
            cou++;
        }
    }
    if(cou != 1){
        ans = "WA";
    }

    print(ans)
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

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

const ll INF = 1e17;
//const ll mod = 1000000007;
vector<ll> dp[5005][2];
int N;
ll A[5005];
vector<int> pathes[5005];

void f(int now, vector<ll> &v1, vector<ll> &v2, vector<ll> &v3, vector<ll> &v4) {
    vector<ll> u1, u2;
    u2.resize(v2.size() + v4.size(), 0);
    for(int i = 0; i < v2.size(); i++) {
        for(int j = 0; j < v4.size(); j++) {
            u2[i+j] |= (v2[i] & v4[j]);
            if(v3[j] < 0) {
                u2[i+j+1] |= v2[i];
            }
        }
    }
    u1.resize(v1.size() + v3.size(), INF);
    for(int i = 0; i < v1.size(); i++) {
        for(int j = 0; j < v3.size(); j++) {
            chmin(u1[i+j], v1[i] + v3[j]);
            if(v3[j] < 0) {
                chmin(u1[i+j+1], v1[i]);
            }
            if(v4[j] == 1) {
                chmin(u1[i+j+1], v1[i]);
            }
        }
    }
    v1.resize(u1.size());
    v2.resize(u2.size());
    for(int i = 0; i < u1.size(); i++) {
        //cerr << i << " " << u1[i] << endl;
        v1[i] = u1[i];
    }
    //cerr << endl;
    for(int i = 0; i < u2.size(); i++) {
        //cerr << i << " " << u2[i] << endl;
        v2[i] = u2[i];
    }
}

void dfs(int now, int from) {
    //cerr << "dfs on " << now << "\n";
    dp[now][0].push_back(A[now]);
    if(A[now] > 0) dp[now][1].push_back(1);
    else dp[now][1].push_back(0);
    for(int a = 0; a < pathes[now].size(); a++) {
        int to = pathes[now][a];
        if(to == from) continue;
        dfs(to, now);
        //cerr << "merging " << to << " to " << now << endl;
        f(now, dp[now][0], dp[now][1], dp[to][0], dp[to][1]);
    }
    /*
    cerr << "---" << now << "---" << endl;
    for(int i = 0; i < dp[now][0].size(); i++) {
        cerr << i << " " << dp[now][0][i] << endl;
    }
    cerr << "\n";
    for(int i = 0; i < dp[now][1].size(); i++) {
        cerr << i << " " << dp[now][1][i] << endl;
    }
    cerr << "--------------" << endl;
    */
}

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    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;
        pathes[u].push_back(v);
        pathes[v].push_back(u);
    }
    dfs(1, -1);
    int ans = N;
    for(int i = 0; i < dp[1][0].size(); i++) {
        if(dp[1][0][i] < 0) chmin(ans, i);
        if(dp[1][1][i]) chmin(ans, i);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 182784
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll=long long;
using Graph = vector<vector<int>>;
using P = pair<int,int>;
using vi = vector<int>;
const int MOD=(int)1e9+7;
const int INF=(int)1e9;
const ll LINF=(ll)1e18;

int main(){
    int n,m;cin>>n>>m;
    vector<vi> s(m);
    vi p(m);
    rep(i,m){
        int k;cin>>k;
        rep(j,k){
            int a;cin>>a;
            s[i].push_back(a);
        }
    }
    rep(i,m) cin>>p[i];
    int ans=0;
    for(int i=0;i<(1<<n);i++){
        bitset<10> bit(i);
        //cout << bit << endl;
        bool ok = true;
        rep(j,m){
            int tmp=0;
            for(int t : s[j]){
                if(bit.test(t-1)) tmp++;
            }
            if(tmp%2!=p[j]){
                ok = false;
                //cout << tmp%2 << " p[" << j << "]= " << p[j] << endl;
                break;
            }
            
        }
        if(ok) ans++;
    }
    cout << ans << endl;
}

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

using namespace std;



int main(){
    int n,m,k,a;
    cin >> n >> m;
    vector<int> sum(m+1);

    for(int i = 0;i < n;i ++){
        cin >> k;
        for(int j = 0;j < k;j ++){
            cin >> a;
            sum.at(a) ++;
        }
    }

    int ans = 0;
    for(int i = 0;i < m+1;i ++){
        if(sum.at(i) == n){
            ans ++;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 4010;

int a[N], b[N], c[N], d[N], e[N], f[N];
bool l[N][N], r[N][N], u[N][N], dd[N][N]; // blocked ? 
bool vis[N][N];

int dir[][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

vi xs({-INF, INF}), ys({-INF, INF});

queue<pi> q;

void BFS(int x, int y) {
	vis[x][y] = 1;
	q.push({x, y});
	while(q.size()) {
		int x = q.front().F, y = q.front().S;
		q.pop();
		for(int i = 0; i < 4; i++) {
			if(i == 0 && u[x][y]) continue;
			if(i == 1 && dd[x][y]) continue;
			if(i == 2 && r[x][y]) continue;
			if(i == 3 && l[x][y]) continue;
			int xx = x + dir[i][0];
			int yy = y + dir[i][1];
			if(xx < 0 || yy < 0) continue;
			if(xx >= xs.size() - 1 || yy >= ys.size() - 1) continue;
			if(vis[xx][yy]) continue;
			vis[xx][yy] = 1;
			q.push({xx, yy});
		}
	}
}

signed main()
{
	IO_OP;
	
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < n; i++) {
		cin >> a[i] >> b[i] >> c[i];
		xs.PB(a[i]);
		xs.PB(b[i]);
		ys.PB(c[i]);
	}
	for(int i = 0; i < m; i++) {
		cin >> d[i] >> e[i] >> f[i];
		xs.PB(d[i]);
		ys.PB(e[i]);
		ys.PB(f[i]);
	}
	sort(ALL(xs));
	sort(ALL(ys));
	xs.resize(unique(ALL(xs)) - xs.begin());
	ys.resize(unique(ALL(ys)) - ys.begin());
	int x = lower_bound(ALL(xs), 0) - xs.begin();
	int y = lower_bound(ALL(ys), 0) - ys.begin();
	x--, y--;
	for(int i = 0; i < n; i++) {
		int aa = lower_bound(ALL(xs), a[i]) - xs.begin();
		int bb = lower_bound(ALL(xs), b[i]) - xs.begin();
		int cc = lower_bound(ALL(ys), c[i]) - ys.begin();
		for(int j = aa; j < bb; j++) {
			u[j][cc-1] = 1;
			dd[j][cc] = 1;
		}
	}
	for(int i = 0; i < m; i++) {
		int ddd = lower_bound(ALL(xs), d[i]) - xs.begin();
		int ee = lower_bound(ALL(ys), e[i]) - ys.begin();
		int ff = lower_bound(ALL(ys), f[i]) - ys.begin();
		for(int j = ee; j < ff; j++) {
			r[ddd-1][j] = 1;
			l[ddd][j] = 1;
		}
	}
	BFS(x, y);
	if(vis[0][0] || vis[xs.size() - 1][ys.size() - 1]) {
		cout << "INF" << endl;
		return 0;
	}
	ll ans = 0;
	for(int i = 0; i < xs.size() - 1; i++) {
		for(int j = 0; j < ys.size() - 1; j++) {
			if(vis[i][j]) {
				ans += (ll) (xs[i + 1] - xs[i]) * (ys[j + 1] - ys[j]);
			}
		}
	}
	cout << ans << endl;
}





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

int main() {
  ll n, k, q;
  cin >> n >> k >> q;
  vector<ll> s(n);
  REP(i, n)
    s.at(i) = 0;
  REP(i, q) {
    ll tmp;
    cin >> tmp;
    --tmp;
    ++s.at(tmp);
  }
  
  REP(i, n) {
    cout << (k + s.at(i) - q > 0 ? "Yes" : "No") << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <cstdlib>
#include <string.h>

using namespace std;

const int digit = 10;

void sort(int Y[], const int N)
{
    int radixes[N] = {};
    int tmpY[N] = {};
    
    const int RadixMax = 1000000000;
    for (int digit = 1; digit <= RadixMax; digit *= 10)
    {
        //! 1, 2, ..., N の digit における基数を求める
        for (int i = 0; i < N; i++)
        {
            radixes[i] = (Y[i] / digit) % 10;
        }
        
        //! ソート
        int insertPos = 0;
        for (int j = 0; j <= 9; j++)
        {
            for (int i = 0; i < N; i++)
            {
                if (radixes[i] == j)
                {
                    tmpY[insertPos] = Y[i];
                    insertPos++;
                }
            }
        }
        
        //! コピー
        for (int i = 0; i < N; i++)
        {
            Y[i] = tmpY[i];
        }
    }
}

int main()
{
    int N;
    cin >> N;
    
    int X[N] = {};
    for (int i = 0; i < N; i++)
    {
        cin >> X[i];
    }

    //! X をソート用配列に全コピ
    int Y[N] = {};
    for (int i = 0; i < N; i++)
    {
        Y[i] = X[i];
    }
    
    sort(Y, N);
    int median = Y[N/2];
    for (int outPos = 0; outPos < N; outPos++)
    {
        if (median > X[outPos])
        {
            cout << median << endl;
        }
        else
        {
            cout << Y[N/2 - 1] << endl;
        }
    }
}

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

fn main() {
    let stdin = io::stdin();
    let mut buf = String::new();
    stdin.read_line(&mut buf).ok();

    let mut it = buf.split_whitespace().map(|n| u64::from_str(n).unwrap());
    let (r, g, b) = (it.next().unwrap(), it.next().unwrap(), it.next().unwrap());

    if (r * 100 + g * 10 + b) % 4 == 0 {
        println!("YES");
        return;
    }
    println!("NO");
}


Measured memory_bytes: 4352
fun main(arr: Array<String>) {
    val n = readLine()!!.toInt()
    val list = readLine()!!.split(" ").map { it.toLong()}
    val total = mutableListOf(list.first())
    list.drop(1).forEach { total.add(total.last() + it) }
    val cnt = mutableMapOf<Long, Int>()
    total.forEach { cnt[it] = (cnt[it]?:0) + 1 }
    var ans = (cnt[0]?:0).toLong()
    cnt.filter { it.value > 1}.forEach { ans += it.value.toLong() * (it.value - 1) / 2 }
    println(ans)
}

Measured memory_bytes: 81784