akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
long long MIN(long long a,long long b){return a<b?a:b;}
int main(){
  long long n,i,j,k,a[410],d[410][410]={};
  scanf("%lld",&n);
  for(i=0;i<410*410;i++)d[i/410][i%410]=1e18;
  for(i=0;i<n;i++)scanf("%lld",&a[i+1]);
  for(i=0;i<n;i++)a[i+1]+=a[i];
  for(i=0;i<n;i++)d[i][i+1]=a[i+1]-a[i];
  for(i=1;i<=n;i++){
    for(j=0;j+i<=n;j++){
      for(k=j;k<=j+i;k++)d[j][j+i]=MIN(d[j][j+i],d[j][k]+d[k][j+i]+a[j+i]-a[j]);
    }
  }
  printf("%lld\n",d[0][n]-a[n]);
  return 0;
}


Measured memory_bytes: 1536
/*
    @uthor: Amit Kumar
    user -->GitHub: drviruses ; CodeChef: dr_virus_ ; Codeforces,AtCoder,Hackerearth,Hakerrank: dr_virus;
*/
#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using namespace std::chrono;
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;
//#define ln mp::cpp_int;
#define ll    long long
#define ld    long double
#define ull   unsigned long long
#define endl "\n"
ll google_itr = 1;
#define google(x) cout<<"Case #"<<x<<":"
#define pi 3.14159265358979323846264338327950L

const ll mod = 1e9+7;
const ll inf = 1e18;

ll popcount(ll num){
    num = num - ((num >> 1) & 0x55555555);
    num = (num & 0x33333333) + ((num >> 2) & 0x33333333);
    return ((num + (num >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

vector<pair<ll,ll>> factor_arr;

void myfactor(ll num){ 
    ll count = 0;   
    while (!(num % 2)) { 
        num >>= 1; count++; 
    }  
    if (count) factor_arr.push_back({2,count}); 
    for (auto i = 3; i <= sqrt(num); i += 2) { 
        count = 0; 
        while (num % i == 0) { 
            count++; 
            num /= i; 
        } 
        if (count) factor_arr.push_back({i,count}); 
    } 
    if (num > 2) factor_arr.push_back({num,1});
}

void virus(){
        ll len;
        ld k;
        cin>>len>>k;
        vector<ld> arr(len);
        for(auto &i:arr) cin>>i;
        ld sum = accumulate(arr.begin(),arr.end(),0);
        sort(arr.begin(),arr.end(),greater<ld>()); 
        ll cnt = 0;
        for(auto i:arr){
            if(i >= (sum/(k*4))) cnt++;
        }
        (cnt >= k)? cout<<"Yes\n":cout<<"No\n";
}


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
  /*#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif*/

    ll t=1;
    //cin>>t;
    while(t--){
           auto start = high_resolution_clock::now();
           virus();
           auto stop = high_resolution_clock::now();
           auto duration = duration_cast<seconds>(stop - start);
         //cout << "Time: "<<duration.count()<<endl;
        //your code goes here
    }
    return 0;
}

Measured memory_bytes: 3788
#include <cstdio>
#include <utility>
#include <algorithm>
#include <map>

const int MAXN = (int)2e5 + 1;

int p[MAXN];
bool is_min[MAXN];  // is_min[i]:p[i]是不是[i,i+k-1]的min?
bool is_max[MAXN];  // is_max[i]:p[i]是不是[i-k+1,i]的max?

// Segment tree
struct Node {
  int min, max;
};
Node node[MAXN << 2];

void build(int rt, int l, int r) {
  if (l == r) {
    node[rt].min = node[rt].max = p[l];
    return;
  }
  int mid = (l + r) / 2;
  build(rt << 1, l, mid);
  build(rt << 1 | 1, mid + 1, r);
  node[rt].min = std::min(node[rt << 1].min, node[rt << 1 | 1].min);
  node[rt].max = std::max(node[rt << 1].max, node[rt << 1 | 1].max);
}

Node query(int ql, int qr, int rt, int l, int r) {
  if (ql <= l && qr >= r) return node[rt];
  int mid = l + r >> 1;
  if (ql > mid) return query(ql, qr, rt << 1 | 1, mid + 1, r);
  else if (qr <= mid) return query(ql, qr, rt << 1, l, mid);
  Node left = query(ql, mid, rt << 1, l, mid);
  Node right = query(mid + 1, qr, rt << 1 | 1, mid + 1, r);
  Node res;
  res.min = std::min(left.min, right.min);
  res.max = std::max(left.max, right.max);
  return res;
}

int solve(int n, int k) {
  for (int i = 1; i <= n; ++i) is_min[i] = is_max[i] = false;

  build(1, 1, n);
  for (int l = 1; l + k - 1 <= n; ++l) {
    int r = l + k - 1;
    Node res = query(l, r, 1, 1, n);
    if (p[l] == res.min) is_min[l] = true;
    if (p[r] == res.max) is_max[r] = true;
  }

  int res = n - k + 1;
  for (int l = 2; l + k - 1 <= n; ++l) {
    if (is_min[l - 1] && is_max[l + k - 1]) --res;
  }
  // printf("%d\n", res);
  std::map<int, int> m;
  int len = 1;
  for (int i = 2; i <= n; ++i) {
    if (p[i] < p[i - 1]) {
      ++m[len];
      len = 1;
    } else {
      ++len;
    }
  }
  ++m[len];
  bool first = true;
  for (const auto &cur : m) {
    int len = cur.first, num = cur.second;
    // printf("len = %d num = %d\n", len, num);
    if (len < k) continue;
    if (first) {
      res -= num - 1;
      first = false;
    } else {
      res -= num;
    }
  }
  return res;
}

int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; ++i) scanf("%d", p + i);
  printf("%d\n", solve(n, k));
  return 0;
}



Measured memory_bytes: 7552
import itertools

N = list(range(1, int(input()) + 1))
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))

a = 0
b = 0
for i, n in enumerate(itertools.permutations(N)):
    if n == P:
        a = i
    if n == Q:
        b = i
print(abs(a - b))

Measured memory_bytes: 9108
#include <bits/stdc++.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
#define pi 3.14159265358979323846264338327950L
using namespace std;

int main() {
  string S, T;
  cin >> S >> T;
  int s=S.size(), t=T.size();
  vector<string> U(s-t+1);
  for (int i=0; i<s-t+1; i++) {
    U[i]=S[i];
  }
  if (t>1) {
    for (int i=0; i<s-t+1; i++) {
      for (int j=1; j<t; j++) {
        U[i]=U[i]+S[i+j];
      }
    }
  }
  vector<int> V(s-t+1);
  for (int i=0; i<s-t+1; i++) {
    V[i]=0;
    for (int j=0; j<t; j++) {
      if (U[i][j]!=T[j]) {
        V[i]++;
      }
    }
  }
  sort(V.begin(),V.end());
  cout << V[0] << endl;
}

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

using namespace std;

using int64 = long long;
const int mod = 998244353;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;


template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {
  os << p.first << " " << p.second;
  return os;
}

template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
  is >> p.first >> p.second;
  return is;
}

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template< typename T >
istream &operator>>(istream &is, vector< T > &v) {
  for(T &in : v) is >> in;
  return is;
}

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
  return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}

template< typename F >
struct FixPoint : F {
  FixPoint(F &&f) : F(forward< F >(f)) {}

  template< typename... Args >
  decltype(auto) operator()(Args &&... args) const {
    return F::operator()(*this, forward< Args >(args)...);
  }
};

template< typename F >
inline decltype(auto) MFP(F &&f) {
  return FixPoint< F >{forward< F >(f)};
}

int main() {
  int N, Y;
  cin >> N >> Y;
  vector< int > A(N);
  cin >> A;
  int64 S = 0;
  for(int i = 0; i < N; i++) {
    A.emplace_back(A[i]);
    S += A[i];
  }
  S /= 5;

  // また誤読しました笑

  auto solve = [&](const vector< int > &X) {
    int64 ok = 0, sum = 0;
    auto adddp = make_v< int64 >(X.size() + 2, 6);
    adddp[0][0] += 1;
    adddp[1][0] -= 1;

    for(int i = 0; i <= X.size(); i++) {
      if(i > 0) {
        for(int j = 0; j < 6; j++) {
          adddp[i][j] += adddp[i - 1][j];
        }
      }
      if(i == X.size()) break;
      while(ok < i || (ok < X.size() && sum + X[ok] + Y < S)) {
        sum += X[ok];
        ++ok;
      }
      if(ok < X.size()) {
        for(int j = 0; j < 5; j++) {
          adddp[ok + 1][j + 1] += adddp[i][j];
        }
      }
      sum -= X[i];
    }
    return adddp[X.size()][5];
  };

  int64 ret = 0;
  for(int i = 0; i < N; i++) {
    int L = i, R = i + N;
    vector< int > S;
    for(int j = L; j < R; j++) S.emplace_back(A[j]);
    ret += solve(S);
  }
  cout << ret / 5 << endl;
}



Measured memory_bytes: 3220
#! usr/bin/perl

use strict;
use warnings;

chomp(my $line = <STDIN>);
my ($N,$M) = split ' ',$line;

my $result = $M * $N - 2* ($M + $N) +4;
if ($N==1) { $result = $M-2}
if ($M==1) { $result = $N-2}
if ($N==2 or $M==2) {$result = 0}
if ($N==1 and $M==1) { $result = 1}

print "$result\n";

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

int main()
{
  i64 n, d;
  cin >> n >> d;
  d = d * 2 + 1;
  cout << (n + d - 1) / d << endl;
  return 0;
}


Measured memory_bytes: 256
a, b = map(int, input().split())
ans = float('inf')
for i in range(1400):
    # print(int(i*0.08), int(i*0.1))
    if a == int(i*0.08) and b == int(i*0.1):
        ans = i
        break

if ans == float('inf'):
    print(-1)
else:
    print(ans)

Measured memory_bytes: 3060
using System;
using System.Linq;

namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var N = input[0];
            var X = input[1];
            var L = Console.ReadLine().Split().Select(int.Parse).ToArray();

            var cnt = 1;
            var d = 0;
            for (int i = 0; i < N; i++)
            {
                d += L[i];
                if (d <= X) cnt++;
                else break;
            }

            Console.WriteLine(cnt);
        }
    }
}

Measured memory_bytes: 13396
#include<string.h>
#include<iostream>
#include<ctype.h>
using namespace std;
int main()
{
	char w[16], wc[16] , t[1024],tc[1024];
	int c = 0;
	cin >> wc;
	strcpy(w, wc);
	for (int i = 0;; i++){
		w[i] = tolower(wc[i]);
		if (wc[i] == '\0')break;
	}
	while (1){
		cin >> tc;
		if (!(strcmp("END_OF_TEXT", tc))){
			break;
		}
		strcpy(t, tc);
		for (int i = 0;; i++){
			t[i] = tolower(tc[i]);
			if (tc[i] == '\0')break;
		}
		if (!(strcmp(w, t))){
			c++;
		}
	}
	cout << c<<endl;
	return 0;
}

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

int main() {
  int n;
  cin >> n;
  vector<int> v(n);
  rep(i, n) cin >> v[i];

  map<int, int> e, o;
  for (int i = 0; i < n; i += 2) {
    if (e.count(v[i]) == 0) e[v[i]] = 0;
    e[v[i]]++;
  }
  for (int i = 1; i < n; i += 2) {
    if (o.count(v[i]) == 0) o[v[i]] = 0;
    o[v[i]]++;
  }

  vector<P> fe, fo;
  for (auto ele : e) fe.push_back({ele.second, ele.first});
  for (auto ele : o) fo.push_back({ele.second, ele.first});
  sort(fe.rbegin(), fe.rend());
  sort(fo.rbegin(), fo.rend());

  int ans = 0;
  if (fe[0].second == fo[0].second) {
    if (fe.size() == 1 && fo.size() == 1) {
      ans = n / 2;
    } else if (fe.size() == 1) {
      ans = n / 2 - fo[0].first;
    } else if (fo.size() == 1) {
      ans = n / 2 - fe[0].first;
    } else {
      ans = n - max(fe[0].first + fo[1].first, fe[1].first + fo[0].first);
    }
  } else {
    ans = n - fe[0].first - fo[0].first;
  }
  cout << ans << endl;
}


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

using namespace std;

const int N = 2e5 + 5;

int n, k, c, tot;
char s[N];
int lf[N], rt[N];

int main() {
  ios::sync_with_stdio(false);
  cin >> n >> k >> c;
  cin >> (s + 1);
  int right = 0; 
  tot = 0;
  for (int i = 1; i <= n; i++) {
    if (s[i] == 'o' && i >= right) 
      lf[++tot] = i, right = i + c + 1;
  }
  if (tot > k)  
    return 0;
  int left = n; 
  for (int i = n, l = 0; i >= 1; i--)
    if (s[i] == 'o' && i <= left)
      left = i - c - 1, rt[tot - (l++)] = i; 
  for (int i = 1; i <= tot; i++)
    if (lf[i] == rt[i])
      cout << lf[i] << '\n';
  return 0; 
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
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; }
typedef long long ll;
int main(void){
    string s;cin>>s;
    map<int,int> mp;
    rep(i,26) mp[i]=0;
    rep(i,s.size())mp[s[i]-'a']++;
    rep(i,26){
        if(mp[i]==0){
            char c=i+'a';
            cout<<c<<endl;
            return 0;
        }
    }
    cout<<"None"<<endl;
}

Measured memory_bytes: 512
use std::io::*;
use std::str::*;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let s = stdin
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok().unwrap()
}

fn main() {
    let n: i32 = read();
    println!("{}", (n + 1) / 2 - 1)
}


Measured memory_bytes: 4352
import std.stdio;
import std.string;
import std.conv;
import std.typecons;
import std.algorithm;
import std.functional;
import std.bigint;
import std.numeric;
import std.array;
import std.math;
import std.range;
import std.container;
import std.ascii;
void times(alias pred)(int n) {
    foreach(i; 0..n) pred();
}
auto rep(alias pred, T = typeof(pred()))(int n) {
    T[] res = new T[n];
    foreach(ref e; res) e = pred();
    return res;
}

void main() {
    string str = readln.chomp.to!string;
    writeln(str.find('C').find('F').length>0 ? "Yes":"No");
}


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

int main() {
	int a, b, r;
	while(cin >> a >> b){
		if(a<b){
			int tmp = a;
			a = b;
			b = tmp;
		}
		r = a%b;
		while(r != 0){
			a = b;
			b = r;
			r = a%b;
		}
		cout << b << endl;
	}
	
	return 0;
}


Measured memory_bytes: 3008
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int main(){
  int a,b;
  cin>>a>>b;

  int ans=0;
  for(int i=1;i<=b-a;i++){
    ans+=i;
  }
  cout<<ans-b<<endl;
  return 0;
}


Measured memory_bytes: 256
N,a,b = list(map(int,input().split()))
Sum_0 = 0

for i in range(N+1):
    i = str(i)
    Sum_1 = 0
    for t in i:
        Sum_1 += int(t)
    if a <= Sum_1 <=b:
        Sum_0+=int(i)
print (Sum_0)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define ll long long
#define M 998244353
#define all(v) (v).begin(),(v).end()
#define fr first
#define sc second
#define sz(x) (ll)((x).size())
#define endl "\n"
#define vc vector
#define pb push_back
#define pii pair<ll,ll>
#define psi pair<string,ll>
#define msi map<string,ll>
#define mii map<ll,ll>
#define mp  make_pair
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define PI 3.14159265
#define mem(x,val) memset(x,val,sizeof(x))
#define r0 return 
const long long INF=1e13;
template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.fr>>a.sc;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.fr<<" "<<a.sc;return out;}
template<typename T,typename T1>T amax(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T amin(T &a,T1 b){if(b<a)a=b;return a;}
#define dbgv(container) {cerr << #container << " : \n"; int cnt = 0; for (auto& x: container) cerr << #container << "[" << cnt++ << "] = " << x << '\n';} 
#define dbgvv(container) {cerr << #container << " : \n"; int c1=0,c2=0; for (auto& x : container){c2 = 0; for (auto& y : x) {cerr << #container << "[" << c1 << "][" << c2++ << "] = " << y << '\n';}c1++;}}
#define dbg(...)__f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << '\n';
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}

//code begins here
ll n,m,dp[100005];
vc<ll> adj[100005];
ll dfs(ll i)
{
	if(dp[i]!=-1) return dp[i];
	dp[i]=0;
	for(auto x:adj[i]) amax(dp[i],dfs(x));
	dp[i]++;
	return dp[i];
}
void solve()
{
 	cin>>n>>m;
 	mem(dp,-1);
 	rep(i,0,m)
 	{
 		ll x,y; cin>>x>>y;
 		adj[x].pb(y);
 	}
 	ll ans=-INF;
 	rep(i,1,n+1) amax(ans,dfs(i));
 	cout<<ans-1;
}
signed main()
{
	fast
	ll t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}


Measured memory_bytes: 7936
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
double logbase(double a, double base)
{
   return log(a) / log(base);
}


int main()
{
  int N;
  cin >> N;
  vector<int> vec(N);
  REP(i,N) cin >> vec.at(i); 
  double best = INF;
  REP(i,100){
    int HP = 0;
    REP(j,N){
      HP += pow((i-vec[j]),2);
    }
    if (HP < best){
      best = HP;
    }
  }

  cout << best << endl;
  
}

Measured memory_bytes: 256
parseInt(x) = parse(Int, x)
parseBigInt(x) = parse(BigInt, x)
parseFloat(x) = parse(Float64, x)
parseBigFloat(x) = parse(BigFloat, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
    x,y=parseMap(split(readline()))
    ans=10^10
    if y>=x
        ans=min(ans,y-x)
    end
    if y>=-x
        ans=min(ans,y+x+1)
    end
    if -y>=x
        ans=min(ans,-y-x+1)
    end
    if -y>=-x
        ans=min(ans,-y+x+2)
    end
    println(ans)
end
main()

Measured memory_bytes: 110952
#include<stdio.h>

int main()
{
  char s[11], t[12];
  scanf("%s", s);
  scanf("%s", t);
  
  int i = 0, isSatisfied = 1;
  while (s[i] != '\0') {
    if (s[i] != t[i]) {
      isSatisfied = 0;
      break;
    }
    i++;
  }
  
  (isSatisfied == 1) ? puts("Yes\n") : puts("No\n");
  
  return 0;
}

Measured memory_bytes: 1664
L, R = map(int, input().split())
ans = 2018
for i in range(L, R):
    for j in range(i + 1, R + 1):
        a = (i * j) % 2019
        if a < ans:
            ans = a
        if ans == 0:
            break
    else:
        continue
    break
print(ans)
            

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

using namespace std;
#define INF 1000000001

int main()
{
    int N,K;
    cin >> N >> K;
    vector<double> ps(N,0);

    for(int i = 0;i < N;i++){
        cin >> ps[i];
        ps[i] = (1 + ps[i])/2;
    }

    double max_E = 0,temp = 0;
    for(int k = 0;k < K;k++) max_E +=ps[k];
    temp = max_E;

    for(int i = 1;i <= N-K;i++){
        temp = temp + ps[i+K-1]- ps[i-1];
        max_E = max(temp,max_E); 
    }
    printf("%.7lf\n",max_E);

}



Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(i=a;i<b;i++)
#define pb push_back
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define lb lower_bound
#define vi vector < ll  int >
#define CLR(a) memset((a),0,sizeof(a))
#define mp make_pair
#define hell 1000000007
#define pc __builtin_popcount
using namespace std;
/*
vector < int > tree(400005);

void buildtree (vector < int > v,int node,int start,int fin)
  {
      if(start==fin)
      {
          tree[node]=v[start];
          return;
      }
      int mid=(start+fin)/2;
      buildtree(v,2*node,start,mid);
      buildtree(v,2*node+1,mid+1,fin);
      tree[node]=tree[2*node]+tree[2*node+1];
  }

 int sum (int node,int tl,int tr,int l , int r)
   {
       if(l>r) return 0;
       if(l==tl and r==tr) return tree[node];
       int mid=(tl+tr)/2;
       return sum(2*node,tl,mid,l,min(r,mid))+sum(2*node+1,mid+1,tr,max(l,mid+1),r);
   }

  void update(int node,int tl , int tr,int pos,int val)
    {
        if(tl==tr) {tree[node]=val; return;}
        int mid=(tl+tr)/2;
        if(pos<=mid)
              update(2*node,tl,mid,pos,val);
        else
            update(2*node+1,mid+1,tr,pos,val);
        tree[node]=tree[2*node]+tree[2*node+1];

    }

*/
vector  < int > callps(string &s)
{
    int i,j=0,n=s.size();
    vector < int > lps(n+1);
    for(i=1;i<n;)
    {
        if(s[i]==s[j])
        {
            lps[i++]=++j;
        }
        else
        {
            if(j==0) i++;
            else{
                j=lps[j-1];
            }
        }
    }
    return lps;
}

int KMP(string &A, string &B)
{
    int n=A.size(),m=B.size(),i,j=0;
    vector < int > lps=callps(B);
    for(i=max(0,n-m);i<n;)
    {
        if(A[i]==B[j])
        {i++,j++;
        }

        else
        {
            if(j==0) i++;
            else{
                j=lps[j-1];
            }
        }
    }
    return j;
}

ll pr (ll x, ll y)
{
    if(!y) return 1;
    ll res=1;
    while(y>1)
    {
        if(y&1) res*=x,res%=hell;
        x*=x; x%=hell;
        y>>=1;
    }
    res*=x; res%=hell;
    return res;

}
ll fact[100050],ifact[100050];
ll inv(ll x)
{
    return pr(x,hell-2);
}

void solve()
{
    ll int i,j=0,r=200,p,q,k,d,y=0,h,flag=1,n,m=0,a=hell,b=hell,h1,h2,a1,b1,a2,w,x,u,f,l,c;
    cin>>n>>k;
    vi vn,vk;
    vn.pb(1); m=n;
    for(i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {   vn.pb(i);
            while(n%i==0) n/=i;
        }
    }
    if(n>1) vn.pb(n);
    set < ll > st; st.insert(1);
    for(i=2;i*i<=k;i++)
    {
        if(k%i==0)
        {   st.insert(i);
            while(k%i==0) k/=i;
        }
    }
  if(k>1)  st.insert(k);
  for(auto it : vn) if(st.count(it)) y++;
  cout<<y;
}


signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--)
    solve();
}


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

const int MAX_N = 110;
const int MAX_V = 100100;

int N;
ll W,weight[MAX_N],value[MAX_N];

ll dp[MAX_N][MAX_V];

int main(){
    cin >> N >> W;
    rep(i,N) cin >> weight[i] >> value[i];

    rep(i,MAX_N) rep(j,MAX_V) dp[i][j] = LINF;
    dp[0][0] = 0;

    rep(i,N){
        for(int sum_v=0;sum_v<MAX_V;sum_v++){

            if(sum_v - value[i] >= 0) dp[i+1][sum_v] = min(dp[i+1][sum_v],dp[i][sum_v-value[i]] + weight[i]);

            dp[i+1][sum_v] = min(dp[i+1][sum_v],dp[i][sum_v]);
        }
    }
    ll res = 0;
    rep(sum_v,MAX_V){
        if(dp[N][sum_v]<=W) res = sum_v;
    }
    cout << res << endl;
}

Measured memory_bytes: 86272
#include<iostream>
using namespace std;
int main()
{
   int x,y; cin>>x>>y;
   if(y&1)
     cout<<"No\n";
  else{
    int crane,fox;
    fox = 2*x;
    crane = 4*x;
    if(y > crane || fox > y)
      cout<<"No\n";
    else
      cout<<"Yes\n";
    
  }
    return 0;
}

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

using namespace std;

string s;

bool is(int i, char c) {
  return i < s.length() && s[i] == c;
}

int main() {
  getline(cin, s);
  for (int i = 0; i < s.length(); i++)
    if (is(i,'a') && is(i+1,'p') && is(i+2,'p') && is(i+3,'l') && is(i+4,'e')) {
      s[i] = 'p';
      s[i+1] = 'e';
      s[i+2] = 'a';
      s[i+3] = 'c';
      s[i+4] = 'h';
    } else if (is(i,'p') && is(i+1,'e') && is(i+2,'a') && is(i+3,'c') && is(i+4,'h')) {
      s[i] = 'a';
      s[i+1] = 'p';
      s[i+2] = 'p';
      s[i+3] = 'l';
      s[i+4] = 'e';
    }
  cout << s << endl;
  return 0;
}

Measured memory_bytes: 0
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

T, X = MAP()
print(T/X)

Measured memory_bytes: 5388
N,M,K=map(int,input().split())

par=[-1]*N
num=[0]*N

def find(x):
    if par[x-1]<0:
        return x
    else:
        par[x-1]=find(par[x-1])
        return par[x-1]

def union(x,y):
    if find(x)==find(y):
        return
    if find(x)>find(y):
        x,y=y,x
    par[find(x)-1]+=par[find(y)-1]
    par[find(y)-1]=find(x)   

def size(x):
    return -par[find(x)-1]

def same(x,y):
    return find(x)==find(y)
        

for _ in range(M):
    a,b=map(int,input().split())
    union(a,b)
    num[a-1]+=1
    num[b-1]+=1

for _ in range(K):
    c,d=map(int,input().split())
    if same(c,d):
        num[c-1]+=1
        num[d-1]+=1

for i in range(N):
    print(size(i+1)-1-num[i],end=" ")


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

int main(){
	for(int i=0; i<205; i++){
      int w;
      cin >> w;
      if(w == -1 ){
        break;
      }else if(0 <= w && w <= 10){
        cout << 4280 - 1150 <<endl;
      }else if(w <= 20){
        cout << 4280 - (1150 + 125*(w - 10)) << endl;
      }else if(w <= 30){
        cout << 4280 - (2400 + 140*(w - 20)) << endl;
      }else{
        cout << 4280 - (3800 + 160*(w - 30)) << endl;
      }
    }
  return 0;
}


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

struct UnionFind {
    vector<int> d;
    UnionFind(int n=0): d(n,-1) {}
    int find(int x) {
        if (d[x] < 0) return x;
        return d[x] = find(d[x]);
    }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if(x==y) return false;
        if(d[x] > d[y]) swap(x,y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    bool same(int x, int y) {return find(x) == find(y);}
    int size(int x) {return -d[find(x)];}
};

int deg[100005];
vector<int> to[100005];
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    UnionFind uf(n);
    rep(i,m) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        deg[a]++;
        deg[b]++;
        uf.unite(a,b);
    }
    rep(i,k) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        to[a].push_back(b);
        to[b].push_back(a);
    }
    rep(i,n) {
        int ans = uf.size(i)-1-deg[i];
        for(int u : to[i]) {
            if(uf.same(i,u)) --ans;
        }
        printf("%d%c", ans, i==n-1?'\n':' ');
    }
    return 0;
}

Measured memory_bytes: 6784
#include <bits/stdc++.h>
using namespace std;
int main () {
  int N, Q;
  string S;
  cin >> N >> Q >> S;
  vector<int> ans(S.size() + 1);
  for(int i = 0; i < S.size() - 1; i++){
    if(S.substr(i, 2) == "AC")ans.at(i + 2) = 1;
  }
  for(int i = 1; i <= S.size(); i++){
    ans.at(i) += ans.at(i - 1);
  }
  int l, r;
  for(int i = 0; i < Q; i++){
    cin >> l >> r;
    cout << ans.at(r) - ans.at(l) << endl;
  }
  return 0;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
int main() {
  int h,w,i,j;
  cin>>h>>w;
  vector<string> a(h);
  for (j=0;j<w+2;j++) cout<<'#';
  cout<<endl;
  for (i=0;i<h;i++) {
    cin>>a.at(i);
    cout<<'#'<<a.at(i)<<'#'<<endl;
  }
  for (j=0;j<w+2;j++) cout<<'#';
  cout<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define PI 3.141592653589793238
#define fastIO(); ios_base::sync_with_stdio(false); cin.tie(NULL);
#define fr(i,a,b) for(int i=a;i<b;i++)
#define f0(a,b) for(int i=a;i<b;i++)
#define fn(b,a) for(int i=b;i>a;i--)
#define dbg(x); cout<<"\n"<<#x<<": "<<x;
#define ret return
#define ub upper_bound
#define lb lower_bound
#define psb push_back
#define psf push_front
#define pof pop_front
#define pob pop_back
#define mp make_pair
#define sq(a) (a)*(a)
#define fs first
#define sc second
#define el "\n"
#define brk break
#define cont continue
#define all(a) a.begin(),a.end()
#define E9 1000000007
#define E5 100007
#define INF 1e18+7
typedef long long int lli;  //  1e-18 to 1e18
typedef vector<int> vi;
typedef multiset<int> msi;
typedef set<int> si;
typedef string str;
typedef priority_queue<int> pqi;
typedef map<int,int> mii;
typedef map<char,int> mci;
typedef vector<long long int> vll;
typedef pair<long long int,long long int> pll;
typedef vector<vector<long long int>> vvll;
typedef long double ld;
void readVec(vi &a,int n){
    a.resize(n);
    f0(0,n) cin>>a[i];
}
void writeVec(vi &a){
	for(int x:a) cout<<x<<" ";
	cout<<el;
}
//----------------------------------------
void solve(){
    int x,n;
    cin>>x>>n;
    mii p;
    f0(0,n){
        int tmp;
        cin>>tmp;
        p[tmp]++;
    }
    int ans(-1);
    f0(0,1e2){
        if(!p[x-i]){
            ans=x-i;
            brk;
        }
        else if(!p[x+i]){
            ans=x+i;
            brk;
        }
    }
    cout<<ans<<el;
 }
int main(){
    fastIO();
    int t(1);
    // cin>>t;
    while(t--) solve();
    ret 0; 
}

Measured memory_bytes: 3648
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) throws IOException{
		Scanner sc = new Scanner(System.in);

		ArrayList<Integer> array = new ArrayList<Integer>();

		for(int i=0;i<10000;i++) {
			int tmp = sc.nextInt();
			if(tmp==0) {
				break;
			}
			array.add(tmp);
			System.out.println("Case " + (i+1) + ": " + array.get(i));
		}
		sc.close();
	}
}


Measured memory_bytes: 45332
N = int(input())

lstA = list(map(int,input().split()))
lstB = list(map(int,input().split()))

x = 0
ans = 0
for i in range(N):
    if ( lstB[i] >= (lstA[i] + lstA[i+1]) ):
        ans += (lstA[i] + lstA[i+1])
        lstA[i+1] = 0
    elif ( lstB[i] > lstA[i] ):
        ans += lstB[i]
        lstA[i+1] = lstA[i] + lstA[i+1] - lstB[i]
    else:
        ans += lstB[i]

print( ans )


Measured memory_bytes: 19156
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
const ll INF = 1LL<<60;
/////////////////////////////////
int main(){
    
    int cnt = 0;
    bool ans = false;
    int n;
    cin>>n;
    rep(i,n){
        int a,b;
        cin >> a >> b;
        if(a==b){
            cnt++;
            if(cnt>2)
                ans = true;
        }
        else
            cnt = 0;
    }
    if(ans)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

Measured memory_bytes: 3632
#!/usr/bin/env python3
import sys
s = [0, 0]
while True:
    line = sys.stdin.readline() 
    if not line: break 
    line = line.rstrip('\r\n') 
    if line.isdigit():
        next
    else:
        words = line.split()
        if words[0] < words[1]:
            s[1] += 3
        elif words[0] > words[1]:
            s[0] += 3
        else:
            s[0] += 1
            s[1] += 1
print(s[0], s[1])



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

int main(){
  
  int a,b,c;
  cin >> a >> b >> c;
  
  
  if( c > a-b ){
    
    cout << c-a+b << endl;
    
  }
  
  else{
    
    cout << 0 << endl;
    
  }
  
}
  


Measured memory_bytes: 3604
N = int(input())
import fractions

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

gcd_start = [0]
gcd_end = [0]

ans = a[0]
gcd_start.append(ans)
for i in range(1, N-1):
    ans = fractions.gcd(ans, a[i])
    gcd_start.append(ans)

ans = a[-1]
gcd_end.append(ans)
for i in range(-2, -N, -1):
    ans = fractions.gcd(ans, a[i])
    gcd_end.append(ans)

ans_max = 0
for i in range(N):
    ans = fractions.gcd(gcd_end[-i-1], gcd_start[i])
    ans_max = max(ans, ans_max)

print(ans_max)

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

using namespace std;

int main()
{
	string X;
	int ans = 0;
	int count = 0;

	cin >> X;

	for (int i = 0; i < X.size(); i++)
	{
		switch (X[i])
		{
		case 'S':
			count++;
			break;
		case 'T':
			if (count > 0)
				count--;
			else
				ans++;
		}
	}

	ans += count;

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 640
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

S = input()
K = getN()
alpha = 'abcdefghijklmnopqrstuvwxyz'
ans = ''
# ループさせてaにできるならする
# できないなら持ち越し
for i in range(len(S) - 1):
    roop = (26 - alpha.index(S[i])) % 26
    if K >= roop:
        K -= roop
        ans += 'a'
    else:
        ans += S[i]

# 最後の一文字について
ans += alpha[(alpha.index(S[-1]) + K) % 26]
print(ans)

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



int main(){
    int n,m;
    cin>>n>>m;
    cout<<(n*(n-1)/2+m*(m-1)/2)<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
using namespace std;

int main(void){
	int w; cin >> w;
	int n; cin >> n;

	int string[w];
	int i=0;
	for(i=0; i<w; i++){
		string[i]=i+1;
	}
	for(i=0;i<n;i++){
		int a,b;
		char c; cin >> a >> c >> b;
		swap(string[a-1],string[b-1]);
	}
	for(i=0;i<w;i++){
		cout << string[i] << endl;
	}
}


Measured memory_bytes: 3024
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,N) repi(i,0,(N))
#define repi(i,a,b) for (int i = (a); i < (b); ++ i)
#define rrep(i,x) for(int i=((int)(x)-1);i>=0;i--)

#define all(v) (v).begin(), (v).end()
#define ios() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define fi first
#define se second
#define t
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using P = pair<int,int>;
constexpr long long MOD = 1e9 + 7;
constexpr long long INF = 1LL << 60;
// UP = 0;RIGHT = 1; DOWN = 2; LEFT =3;
const int dx[] = {0, 1, 0, -1},
          dy[] = {1, 0, -1, 0};
template<class T = int> bool chmin(T& a, T b) { bool f = a > b; a = f ? b : a; return f;}
template<class T = int> bool chmax(T& a, T b) { bool f = a < b; a = f ? b : a; return f;}

template<class T> istream& operator>>(istream &is,vector<T> &st){
  for(size_t i=0;i<st.size();++i) is >> st[i];
  return is;
}
template<class T> ostream& operator<<(ostream &os, const vector<T> &st){
  for(size_t i=0;i<st.size();++i){
    if(i==st.size()-1) os << st[i];
    else os << st[i] << " ";
  }
  return os;
}
template<class T> istream& operator>>(istream &is,vector<vector<T>> &st){
  for(size_t i=0;i<st.size();++i) is >> st[i];
  return is;
}
template<class T> ostream& operator<<(ostream &os, const vector<vector<T>> &st){
  for(size_t i=0;i<st.size();++i){
    os << st[i];
    if(i!=st.size()-1) os << endl;
  }
  return os;
}
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p){
  return s << "(" << p.first << ", " << p.second << ")";
}


signed main() { 
  ios();
  int N;
  cin >> N;
  vi v(N);
  cin >> v;
  sort(all(v));
  double ans = v[0];
  rep(i, N - 1) {
    ans =  (ans + v[i + 1]) / 2.0;
  }
  cout << fixed << setprecision(7) << ans << endl;
}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val s = readLine()!!
    val n = s.length

    val s1 = s.substring(0, (n - 1) / 2)
    val s2 = s.substring((n + 3) / 2 - 1, n)

    if (s == s.reversed() && s1 == s1.reversed() && s2 == s2.reversed()) {
        println("Yes")
    } else {
        println("No")
    }
}

Measured memory_bytes: 33684
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define ALL(A) A.begin(), A.end()

using namespace std;

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

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	string S; cin >> S;
	int n = (int)S.length();
	stack<int> st;

	int res = 0;
	st.push((int)(S[0] - '0'));
	for (int i = 1; i < n; ++i){
		if (!st.empty() && st.top() != (int)(S[i] - '0')){
			st.pop(); res += 2;
		}else{
			st.push((int)(S[i] - '0'));
		} // end if
	} // end for
	cout << res << endl;
				
	return 0;
}

Measured memory_bytes: 720
from bisect import bisect_left
n, m , k = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

cum_A = [A[0]]
for i in range(1, n):
    cum_A.append(cum_A[-1]+A[i])
cum_B = [B[0]]
for i in range(1, m):
    cum_B.append(cum_B[-1]+B[i])
ans = 0
for i in range(n+1):
    #  i is the number of book from A
    if i == 0:
        target = k
        ind = bisect_left(cum_B, target+0.5)
        ans = max(ans, i+ind)
    else:
        tmp_ans = cum_A[i-1]
        if tmp_ans > k:
            break
        target = k - tmp_ans
        ind = bisect_left(cum_B, target+0.5)
        ans = max(ans, i+ind)
print(ans)

Measured memory_bytes: 48420
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<stdbool.h>
#include<vector>
#include<algorithm>
#include<string>
typedef long long ll;
using namespace std;

int main(void) {
	ll n, m;
	cin >> n >> m;
	if (n == 1) {
		if (m == 1)cout << 1 << endl;
		else {
			if (m == 2)cout << 0 << endl;
			else cout << m - 2 << endl;
		}
	}
	else {
		if (n == 2)cout << 0 << endl;
		else {
			if (m == 1)cout << n - 2 << endl;
			else {
				if (m == 2)cout << 0 << endl;
				else cout << (n - 2)*(m - 2) << endl;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 256
"""

https://atcoder.jp/contests/arc083/tasks/arc083_c

NもXも小さい→重みで場合分けできる？
白と黒は、片方が重み0でなくてはいけないという制約以外は独立
木dpを考える

dp[v][black][white] = vの子部分木の重みの和がそれぞれblとwhの時の割り当てが可能か
→bitsetとかも思いつくが、blかwhはX[i]になることを利用して計算量を削減する

重みは根のほうでいくらでも大きくできるが、小さくはできないことに注目

dp[v][color] = 頂点vをcolorにした場合の、colorでない頂点の合計の最小値
dp[v][black] を求めたい。黒にするためには、黒の合計がXi以下でなくてはならない
→それぞれの子から2通りの bl,whをもらう。うまく組み合わせて、blがXi以下を保ちつつ、whの最小値を出す

これは以下のようなdpで解ける
dpv[i][bl] = wh → i番目の子まで見て、blの合計がblの時のwhの最小値
O(子の数*Xi)で解けるので、全体ではO(N*max(X))ぐらいで解けるはず
→どうしてもblの合計がXi以下にならない場合、不可能

"""
import sys
from sys import stdin

def dfs(v,p):

    dpB = {}
    dpW = {}
    dpB[0] = 0
    dpW[0] = 0

    for nex in lis[v]:

        if nex != p:
            ndpB = {}
            ndpW = {}
        
            b1,w1,b2,w2 = dfs(nex,v)

            for b in dpB:
                if b+b1 > X[v]:
                    continue
                if b+b1 not in ndpB:
                    ndpB[b+b1] = float("inf")
                ndpB[b+b1] = min(ndpB[b+b1],dpB[b] + w1)
            for b in dpB:
                if b+b2 > X[v]:
                    continue
                if b+b2 not in ndpB:
                    ndpB[b+b2] = float("inf")
                ndpB[b+b2] = min(ndpB[b+b2],dpB[b] + w2)

            for w in dpW:
                if w+w1 > X[v]:
                    continue
                if w+w1 not in ndpW:
                    ndpW[w+w1] = float("inf")
                ndpW[w+w1] = min(ndpW[w+w1] , dpW[w] + b1)
            for w in dpW:
                if w+w2 > X[v]:
                    continue
                if w+w2 not in ndpW:
                    ndpW[w+w2] = float("inf")
                ndpW[w+w2] = min(ndpW[w+w2] , dpW[w] + b2)

            dpB = ndpB
            dpW = ndpW
    
    b1 = X[v]
    w1 = float("inf")
    for i in dpB:
        w1 = min(w1,dpB[i])
    w2 = X[v]
    b2 = float("inf")
    for i in dpW:
        b2 = min(b2,dpW[i])

    if w1 == float("inf") and b2 == float("inf"):
        print ("IMPOSSIBLE")
        sys.exit()

    print (dpB,dpW,file=sys.stderr)
    return b1,w1,b2,w2
                    

N = int(stdin.readline())

P = list(map(int,stdin.readline().split()))
X = list(map(int,stdin.readline().split()))

lis = [ [] for i in range(N) ]
for i in range(1,N):
    lis[i].append(P[i-1]-1)
    lis[P[i-1]-1].append(i)

print(dfs(0,0),file=sys.stderr)
print ("POSSIBLE")


Measured memory_bytes: 73124
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <functional>
#include <queue>
//#include <stack>
#include <climits>
#include <map>
#define Rep(i,n) for(int i=0;i<n;i++)
#define For(i,n1,n2) for(int i=n1;i<n2;i++)
#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,n1,n2) for(ll i=n1;i<n2;i++)
#define put(a) cout<<a<<endl;
#define all(a)  (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
using namespace std;
typedef long long ll;
//typedef unsigned long long ull;
typedef pair<int, int> P;
int h,w,n;

int main() {
    cin >> h >> w >> n;
    vector<int> a(n);
    vector<int> b(n);
    REP(i,n){
        cin >> a[i] >> b[i];
    }
    map<P,int> mp;
    REP(i,n){
        FOR(j,-1,2){
            FOR(k,-1,2){
                if(1<(a[i]+j)&&(a[i]+j)<h&&1<(b[i]+k)&&(b[i]+k)<w){
                    P p = make_pair(a[i]+j,b[i]+k);
                    auto iter = mp.find(p);
                    if(iter!=end(mp)){
                        iter->second++;
                    }else{
                        mp.insert(make_pair(p,1));
                    }
                }
            }
        }
    }
    vector<ll> res(10,0);
    ll ca = 0;
    for(auto x : mp){
        res[x.second]++;
        ca++;
    }
    res[0] = max((ll)(h-2)*(w-2)-ca,(ll)0);
    REP(i,res.size()){
        put(res[i]);
    }
    return 0;
}


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

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ for(auto it : P) { s << "<" << it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ for(auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s << endl; }

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define ddrep(i, n) for (int i = n; i > 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define ssrep(i, s, t) for (int i = s; i <= t; ++i)

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; }

using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using ld = long double;
using str = string;

#define rng(a) a.begin(), a.end()
#define rrng(a) a.rbegin(), a.rend()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

long int M = 1e+9+7;
int inf = 1e+9;

int n;
int solve(){
    int ans=0;
    return ans;
}

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << std::setprecision(10);

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

Measured memory_bytes: 3656
using System;

class B {
    public static void Main() {
        var line = Console.ReadLine().Split();
        var n = int.Parse(line[0]);
        var k = int.Parse(line[1]);
        var answer = k;
        for (int i = 1; i < n; ++i) answer *= k - 1;
        Console.WriteLine(answer);
    }
}


Measured memory_bytes: 11092
#include "bits/stdc++.h"

using ll = long long;
using namespace std;

const int N = 2e9;

void solveCase() {

   int n;
   cin >> n;
   vector <ll> v(n);
   for(auto &e: v) {
      cin >> e;
   }
   map <ll, int> m;
   m[0] = 1;
   ll ans = 0;
   for(int i = 0; i < n; i++) {
      if(i > 0)
         v[i] += v[i - 1];
      ans += m[v[i]];
      m[v[i]]++;
   }
   cout << ans << endl;
}


int main() {
   cin.tie(0);
   cin.sync_with_stdio(0);
   
   int testcase = 1;
   // cin >> testcase;
 
   for(int i = 0; i < testcase; i++) {
      solveCase();
   }
 
   return 0;
}


Measured memory_bytes: 17104
#include<iostream>
#include<algorithm>
using namespace std;
const int BUF = 105;


int nVal;
int val[BUF];

void read() {
    cin >> nVal;
    for (int i = 0; i < nVal; ++i) {
        cin >> val[i];
    }
}


void work() {
    sort(val, val + nVal);
    
    int cnt = 0;
    for (int i = 0; i < nVal; ++i) {
        for (int j = i + 1; j < nVal; ++j) {
            for (int k = j + 1; k < nVal; ++k) {
                if (val[i] == val[j] || val[i] == val[k] || val[j] == val[k]) continue;
                if (val[i] + val[j] <= val[k]) continue;
                ++cnt;
            }
        }
    }
    cout << cnt << endl;
}


int main() {
    read();
    work();
    return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;
#define mod 1000000007
#define MAX 100001
#define f(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rf(i,a,b) for(ll i=(ll)(a);i>=(ll)(b);i--)
#define pb push_back
#define pf push_front
#define nl cout << "\n";

const ll INF=1e18L+5;
 
//void ini(){
//	#ifndef ONLINE_JUDGE
//		freopen("input.txt","r",stdin);
//		freopen("output.txt","w",stdout);
//	#endif
//}

ll v[101],w[101];

int main(){
	//ini();
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	
    ll n,wt,sum_val=0;
    cin >> n >> wt;
    f(i,1,n+1){
    	cin >> w[i]>> v[i];
    	sum_val+=v[i];
    }

    vector<ll> dp(sum_val*n+1,INF);
    dp[0]=0;
    f(i,1,n+1){
    	rf(j,sum_val-v[i],0){
    		dp[j+v[i]]=min(dp[j+v[i]],dp[j]+w[i]);
    	}
    }

    ll ans=0;
    f(i,0,sum_val+1){
    	if(dp[i]<=wt){
    		ans=max(ans,i);
    	}
    }

    cout << ans;

}

Measured memory_bytes: 78336