akhauriyash/Code-Regression huggingface dataset:
use proconio::{fastout, input};
use std::io::*;
use std::str::FromStr;

use std::cmp::{max, min};

fn main() {
    input! {
        n:usize,
        d: [i64;n],
    }

    let mut d = d;
    d.sort();
    let mut cnt = 0;
    for i in 0..*d.iter().max().unwrap() {
        let idx = d.upper_bound(i);
        if idx == n / 2 {
            cnt += 1;
        }
    }
    println!("{}", cnt);
}

use std::cmp::Ordering;

pub trait BinarySearch<T> {
    fn lower_bound(&self, x: T) -> usize;
    fn upper_bound(&self, x: T) -> usize;
}

impl<T: Ord> BinarySearch<T> for [T] {
    fn lower_bound(&self, x: T) -> usize {
        let mut low = 0;
        let mut high = self.len();

        while low != high {
            let mid = (low + high) / 2;
            match self[mid].cmp(&x) {
                Ordering::Less => {
                    low = mid + 1;
                }
                Ordering::Equal | Ordering::Greater => {
                    high = mid;
                }
            }
        }
        low
    }
    fn upper_bound(&self, x: T) -> usize {
        let mut low = 0;
        let mut high = self.len();

        while low != high {
            let mid = (low + high) / 2;
            match self[mid].cmp(&x) {
                Ordering::Less | Ordering::Equal => {
                    low = mid + 1;
                }
                Ordering::Greater => {
                    high = mid;
                }
            }
        }
        low
    }
}


Measured memory_bytes: 3788
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;

int main(void) {

    int X, N;
    cin >> X >> N;

    int p[N];
    for (int i = 0; i < N; i++) cin >> p[i];
    sort(p, p + N);
    
    map<int, int> mp;
    int counter = 0;
    for (int i = p[0] - 1; i <= p[N - 1]; i++) {
        if (i == p[counter]) { mp[i] = 1; counter++; }
        else mp[i] = 0;
    }

    int f_ans = X, b_ans = X;
    while (mp[f_ans] != 0 && mp[b_ans] != 0) {
        f_ans++;
        b_ans--;
    }
    if (mp[b_ans] == 0) cout << b_ans << '\n';
    else cout << f_ans << '\n';
    
    return 0;
}


Measured memory_bytes: 3188
#include<bits/stdc++.h>
//#include<boost/multiprecision/cpp_int.hpp>
using namespace std;
//namespace mp=boost::multiprecision;
#define ll long long
int main()
{
    string a,b;cin>>a>>b;
    ll la=a.length();
    ll lb=b.length();
    ll dp[la+1][lb+1]={};
    for(ll i=0;i<=la;i++)
    {
        for(ll j=0;j<=lb;j++)
        {
            if(i==0)
                dp[0][j]=0;
            else if(j==0)
                dp[i][0]=0;
            else if(a[i-1]==b[j-1])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    //cout<<dp[la][lb];
    ll lc=dp[la][lb];
    //cout<<"Length of longest common subsequence:"<<lc<<endl;
    char c[lc+1];
    c[lc]='\0';
    ll i=la,j=lb,k=lc-1;
    while(i>0 && j>0 && k>=0)
    {
        if(dp[i][j]==dp[i-1][j])
            i--;
        else if(dp[i][j]==dp[i][j-1])
            j--;
        else
        {
            c[k]=a[i-1];
            i--;j--;k--;
        }
    }
    cout<<c;
}



Measured memory_bytes: 70656
n = int(input())
p = list(map(int,input().split()))
i = 1
c = 0
while(i<n-1):
    if ((p[i-1] < p[i] and p[i] < p[i+1]) or (p[i+1] < p[i] and p[i] < p[i-1])):
        c += 1
    i += 1
print(c)

Measured memory_bytes: 3060
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <numeric>
#include <string.h>
using namespace std;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<29;
const long long  INFL = 1e18;
const int MOD = 1000000007;
const int MAX = 210000;
const int MAX_NUM = 999999999;
long long N;
vector<long long> X(1009), Y(1009), H(1009);
vector<tuple<long long, long long, long long>>vec;
void solve() {
    cin >> N;
    tuple<long long, long long, long long>G = make_tuple(-1, -1, -1);
    for (int i = 0; i < N; i++) {
        cin >> X[i] >> Y[i] >> H[i];
        if (H[i] >= 1) G = make_tuple(X[i], Y[i], H[i]);
    }
    for (int i = 0; i <= 100; i++) {
        for (int j = 0; j <= 100; j++) {
            long long V = get<2>(G) + abs(get<0>(G) - i) + abs(get<1>(G) - j);
            //V = max(V, 0LL);
            bool flag = true;
            for (int k = 0; k < N; k++) {
                long long VV = V - abs(X[k] - i) - abs(Y[k] - j);
                VV = max(VV, 0LL);
                if(H[k] != VV) flag = false;
            }
            if (flag == true) vec.push_back(make_tuple(i, j, V));
        }
    }
    if (vec.size() == 1) {
        cout << get<0>(vec[0]) << " " << get<1>(vec[0]) << " " << get<2>(vec[0]) << endl;
    }
    return;
}
//逆元を求める関数
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++) {
      fac[i] = fac[i-1] * i % MOD;
      inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
      finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
//組み合わせ
long long COM (int n, int k) {
    if(n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}
int main(int args, char* argv[]) {
    solve();
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(v) v.begin(), v.end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort((c).begin(),(c).end())
#define dbug(x) cout<<#x<<"="<<x<<endl
#define m0(x) memset(x,0,sizeof(x))
#define rep(i, n) for(int i = 0; i < n; i++)
#define repr(i, n) for(int i = n; i >= 0; i--)
#define reps(i, m, n) for(int i = m; i < n; i++)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pl;

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

const int MAXN = 300003;
vector<int> G[MAXN]; //ノードにつながる辺の集合、どこのnode(int)につながっているか
int depth[MAXN]; //ノードの深さ(スタートからの距離),行ったことあるなら正,ないなら-1

int bfs(int s, int g) {
    fill(depth, depth+MAXN, -1);
    deque<int> dq; //探索予定地
    //set<int> st;//探索終了地 setを使わなくてもdepthで足りてる気がする
    dq.push_back(s); // 始点を探索予定地に
    depth[s]=0; // 始点の深さを0に
    while(!dq.empty()) {
        int v = dq.front();
    //    st.insert(v); //vを探索終了地に
        dq.pop_front(); //左から出す
        for(int i = 0; i < (int)G[v].size(); ++i) {
            int e = G[v][i];//行き先
            if(depth[e]==-1) {
              depth[e]=depth[v]+1;
              dq.emplace_back(e);
            }
        }
    }
    if (depth[g]==-1) return -1;
    return depth[g]/3;
}

int main() {
    int N,M;
    cin>>N>>M;
    for (int i = 0; i < M; i++) {
        int a,b; cin>>a>>b;
        G[a].push_back(N+b);
        G[N+a].push_back(2*N+b);
        G[2*N+a].push_back(b);
    }
    int S,T;
    cin>>S>>T;
    cout << bfs(S,T) << endl; // 始点 s から g への最短距離を計算
    return 0;
}


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

using namespace std;

#define all(x) (x).begin(), (x).end()
typedef long double ld;
typedef long long ll;

const int M = 303;

int n;
string s;
int k;
int d[M][M][M];

void read() {
  cin >> s >> k;
  n = s.length();
}

void uax(int &x, int y) {
  x = max(x, y);
}

void kill() {
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
      for (int t = 0; t <= k; ++t) {
        int cur = d[i][j][t];
        if (s[i] == s[n - 1 - j])
          uax(d[i + 1][j + 1][t], cur + 1);
        else
          uax(d[i + 1][j + 1][t + 1], cur + 1);
        uax(d[i + 1][j][t], cur);
        uax(d[i][j + 1][t], cur);
      }

  int ans = 0;
  for (int i = 0; i < n; ++i)
    for (int j = 0; i + j < n; ++j)
      for (int t = 0; t <= k; ++t)
        uax(ans, 2 * d[i][j][t] + 1);

  for (int i = 0; i < n; ++i)
    for (int j = 0; i + j <= n; ++j)
      for (int t = 0; t <= k; ++t)
        uax(ans, 2 * d[i][j][t]);

  cout << ans << endl;
}

int main() {
#ifdef LOCAL
  assert(freopen("d.in", "r", stdin));
#endif

  ios_base::sync_with_stdio(false);

  read();
  kill();

}



Measured memory_bytes: 108800
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace Tasks
{
    public class E
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var (H, W, K) = Scanner.Scan<int, int, int>();
            var S = new bool[H][].Select(x => Scanner.Scan<string>().Select(x => x == '1').ToArray()).ToArray();
            var answer = (int)1e9;
            for (var b = 0; b < 1 << (H - 1); b++)
            {
                var (cutH, cutW) = (0, 0);
                var map = new int[H];
                for (var i = 0; i < H - 1; i++)
                {
                    map[i] = cutH;
                    if ((b >> i & 1) == 1) cutH++;
                }
                map[H - 1] = cutH;
                var count = new int[cutH + 1];
                var ok = true;
                for (var j = 0; j < W && ok; j++)
                {
                    var tmp = count.ToArray();
                    for (var i = 0; i < H; i++)
                        if (S[i][j]) tmp[map[i]]++;
                    if (tmp.Any(x => x > K))
                    {
                        if (j == 0) ok = false;
                        else
                        {
                            cutW++;
                            for (var i = 0; i <= cutH; i++)
                                count[i] = tmp[i] - count[i];
                        }
                    }
                    else count = tmp.ToArray();
                }
                if (ok) answer = Math.Min(answer, cutH + cutW);
            }
            Console.WriteLine(answer);
        }

        public static class Scanner
        {
            private static Queue<string> queue = new Queue<string>();
            public static T Next<T>()
            {
                if (!queue.Any()) foreach (var item in Console.ReadLine().Trim().Split(" ")) queue.Enqueue(item);
                return (T)Convert.ChangeType(queue.Dequeue(), typeof(T));
            }
            public static T Scan<T>() => Next<T>();
            public static (T1, T2) Scan<T1, T2>() => (Next<T1>(), Next<T2>());
            public static (T1, T2, T3) Scan<T1, T2, T3>() => (Next<T1>(), Next<T2>(), Next<T3>());
            public static (T1, T2, T3, T4) Scan<T1, T2, T3, T4>() => (Next<T1>(), Next<T2>(), Next<T3>(), Next<T4>());
            public static (T1, T2, T3, T4, T5) Scan<T1, T2, T3, T4, T5>() => (Next<T1>(), Next<T2>(), Next<T3>(), Next<T4>(), Next<T5>());
            public static IEnumerable<T> ScanEnumerable<T>() => Console.ReadLine().Trim().Split(" ").Select(x => (T)Convert.ChangeType(x, typeof(T)));
        }
    }
}


Measured memory_bytes: 46980
#include <bits/stdc++.h>
using namespace std; 
int main(){
int n,k;
string s;
cin>>n;
cin>>s;
cin>>k;
char check=s[k-1];
for(int i=0; i<n; i++){
if(s[i]!=check)  s[i] = '*';
}
cout<<s<<endl;
}

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

using Lint=long long;
template<int mod> class ModInt
{   
 private:
    Lint val;
 public:
    Lint value(){ return val; }
    ModInt(Lint x=0){ val=x%mod; }
    ModInt pow(int n){
        ModInt res(1),x(val);
        while(n>0){ if(n&1) res*=x; x*=x; n>>=1; }
        return res;
    }
    ModInt inv(){ return pow(mod-2); }
    ModInt& operator+=(ModInt rhs){ val+=rhs.val; if(val>=mod) val-=mod; return *this; }
    ModInt& operator-=(ModInt rhs){ val+=mod-rhs.val; if(val>=mod) val-=mod; return *this; }
    ModInt& operator*=(ModInt rhs){ val=val*rhs.val%mod; return *this; }
    ModInt& operator/=(ModInt rhs){ *this*=rhs.inv(); return *this; }
    ModInt operator+(ModInt rhs){ return ModInt(val)+=rhs; }
    ModInt operator-(ModInt rhs){ return ModInt(val)-=rhs; }
    ModInt operator*(ModInt rhs){ return ModInt(val)*=rhs; }
    ModInt operator/(ModInt rhs){ return ModInt(val)/=rhs; }
};
using mint=ModInt<1000000007>;

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

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

    vector<int> cnt(N+1);
    cnt[0]=3;
    mint ans=1;
    for(int i=0;i<N;i++){
        ans*=cnt[a[i]-1];
        cnt[a[i]-1]--;
        cnt[a[i]]++;
    } 
    cout<<ans.value()<<endl;
    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,n) for(int i=(s);i<(int)(n);i++)
int main(){
  int n,x;
  cin>>n;
  vector<int> a(n+1);
  vector<int> b(n+1);
  rep(i,1,n+1){
    cin>>a.at(i);
    b.at(a.at(i))=i;
  }
  rep(i,1,n+1){
    cout<<b.at(i)<<endl;
}
}

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

int main() {
  long n,m,ans=0;
  cin >> n >> m;
  vector<pair<long,long>> b(n,pair<long,long>());
  for(int i=0;i<n;i++) cin >> b[i].first >> b[i].second;
  sort(b.begin(),b.end());
  for(int i=0;true;i++) {
    if(b.at(i).second<m) {
      m-=b.at(i).second;
      ans+=b.at(i).second*b.at(i).first;
    } else {
      ans+=m*b.at(i).first;
      break;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 1792
N = gets.chomp.to_i
t0, x0, y0 = 0, 0, 0
readlines.each do |line|
  t, x, y = line.chomp.split(' ').map(&:to_i)
  dx = (x - x0).abs
  dy = (y - y0).abs
  if t - t0 - dx - dy >= 0 && (t - t0 - dx - dy) % 2 == 0
    t0, x0, y0 = t, x, y
  else
    puts :No
    exit
  end
end
puts :Yes


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

int main() {
    int m1, d1, m2, d2; cin >> m1 >> d1 >> m2 >> d2;
    if(m1 == 12 && d1 == 31){
        cout << 1 << endl;
    } else if(m1 < m2){
         cout << 1 << endl;
     } else{
        cout << 0 << endl;
    }
    
	return 0;
}

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

vector<ll>multiple(1000005);
void prime(int v){
  multiple[0]=-1;
  multiple[1]=-1;
  for(int i=2; i<=v; i++){
    if(multiple[i]!=0)continue;
    for(int j=i*2; j<=v; j+=i){
     multiple[j]=i;
    }
  }
}

int main(){
  ll n;
  cin >> n;
  prime(1000000);
  ll count=0;
  ll num=n;
  for(int i=0; i<=1000000; i++){
    if(multiple[i]!=0) continue;
    while(num%i==0){
      num/=i;
    }
  }

  ll remain=num;
  
  
  num=n;
  for(int i=0; i<=1000000; i++){
    if(multiple[i]!=0) continue;
    ll j=1;
    ll waru=pow(i,j);
    while(num%waru==0){
      num/=waru;
      count++;
      j++;
      waru=pow(i,j);
    }
  }
  if(remain!=1) count++;
  cout << count << endl;
}
  
  
  


Measured memory_bytes: 11028
#include<bits/stdc++.h>
#define int unsigned long long 

using namespace std;
int32_t  main(){
     string a,b;
     cin>>a>>b;
     int c = 0;
     for(int i=0;i<a.size();++i){
          if(a[i]!=b[i]){
              c++;
          }
     }
     cout<<c;
    
}

Measured memory_bytes: 3912
#include <iostream>
#include <stdlib.h>
using namespace std;

struct list{
  int number;
  list *next;
};

void Insertlist(list ** ptr, int newnumber){
  if( *ptr == NULL || (*ptr)->number < newnumber){
    list *newcell;
    newcell = (list *)malloc(sizeof(list));
    newcell->number = newnumber;
    newcell->next = *ptr;
    *ptr = newcell;
  }else{
    Insertlist(&(*ptr)->next, newnumber);
  }
}

int main(){

  int n, r;

  while( cin >> n >> r ){

    if( n == 0 && r == 0) break;

    list *root = NULL;
    for(int i = n ; i > 0 ; i--){
      Insertlist(&root,i);
    }
 
    while( r ){
      int p,c;
      cin >> p >> c;

      list *ptr1 = root, *ptr2 = root,*ptr3,*ptr4;
      
      for(int i = 0 ; i < p-2; i++)
	ptr1 = ptr1->next;
      if(p > 1)
	ptr2 = ptr1->next;
      ptr3 = ptr2;
      for(int i = 0; i < c-1 ; i++)
	ptr3 = ptr3->next;
      ptr4 = ptr3->next;
      
      if(p>1){
	ptr1->next = ptr4;
	ptr3->next = root;
	root = ptr2;
      } 
      r--;
    }
    cout << root->number << endl;
  }
  return 0;
}

Measured memory_bytes: 1528
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll mod = 1e9+7;

int main(){
    ll n;
    cin >> n;
    ll a,b;
    cin >> a >> b;
    ll c = a+b;
    if(n%c >= a) cout << a*(n/c)+a << endl;
    else cout << a*(n/c)+n%c << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace __gnu_pbds;
using namespace std;
 
typedef long long int ll;
typedef unsigned long long int sll;
typedef  double ld;
#define A 1000000007ll
#define D 100000000000000ll
#define B 998244353ll
#define C 1000000000000000000ll
#define M 4000
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define oset tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define mxe(v) *max_element(v.begin(),v.end())
#define mne(v) *min_element(v.begin(),v.end())
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define ve vector
#define br break
#define PI acos(-1)
#define subt cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n" 

bool ab[10005],ac[10005],bc[10005];

int main() 
{
    FAST;
    string a,b,c;
    cin>>a>>b>>c;
    for(int i=0;i<a.length();i++)
        for(int j=0;j<b.length();j++)
            if(a[i]!=b[j] && a[i]!='?' && b[j]!='?')
                ab[i-j+M]=1;
    for(int i=0;i<a.length();i++)
        for(int j=0;j<c.length();j++)
            if(a[i]!=c[j] && a[i]!='?' && c[j]!='?')
                ac[i-j+M]=1;
    for(int i=0;i<b.length();i++)
        for(int j=0;j<c.length();j++)
            if(b[i]!=c[j] && b[i]!='?' && c[j]!='?')
                bc[i-j+M]=1;
    ll ans=a.length()+b.length()+c.length(),x=(ll)a.length()+(ll)b.length()+(ll)c.length();
    for(int i=-M;i<M;i++)
        for(int j=-M;j<M;j++)
            if(!ab[i+M] && !ac[j+M] && !bc[j-i+M])
            {
                ll l,r;
                l=min(0,min(i,j));
                r=max((ll)a.length(),max((ll)b.length()+i,(ll)c.length()+j));
                ans=min(ans,r-l);
            }
    cout<<ans;
    subt;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<stdio.h>
#include<string>
using namespace std;
#define pb push_back
#define pf push_front

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

#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define sz(x) int(x.size())
#define INF 1e5

int main(){
	int n,k;
	cin>>n>>k;
	string s;
	cin>>s;
	int score=0;
	rep(i,n-1){
		if(s[i]==s[i+1]) score++; 
	}
	int ans = min(score+2*k,n-1);
	cout<<ans<<endl;
}

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


#define M_MAX 20
#define N_MAX 50000
#define INFTY 1 << 29

int main(){
int n;
cin >> n;
int h[n];
int maxi=0;
int count=0;
for(int i=0;i<n;i++){
cin >> h[i];
if(maxi<=h[i])count++;
maxi=max(maxi,h[i]);
}
cout << count;

}


Measured memory_bytes: 256
N,K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))

A.sort()
F.sort(reverse=True)

def is_ok(m):
    c = 0
    for a,f in zip(A,F):
        d = m//f
        c += max(0, a-d)
        if c > K:
            return False
    return True

ok = 10**13
ng = -1
while ok-ng > 1:
    m = (ok+ng)//2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)

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

#define fi first
#define se second

typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<vii> vvii;
typedef vector<int>::iterator vit;

const int MAXN = 100005;
const int LOGN = 20;

int idx[MAXN]; // i : index of node i in dfs path
ii path[MAXN << 1];
vi adjList[MAXN];

ii ST[LOGN][MAXN<<1];

void build(int n) {
    int h = (n == 1 ? 1 : ceil(log2(n)));

    for (int i = 0; i < n; i++) ST[0][i] = path[i];
    for (int i = 1; i < h; i++)
        for (int j = 0; j + (1<<i) <= n; j++)
            ST[i][j] = min(ST[i-1][j], ST[i-1][j+(1<<(i-1))]);
}

int RMQ(int l, int r) {    // range [l,r)
    int p = 31 - __builtin_clz(r-l);
    return min(ST[p][l],ST[p][r-(1<<p)]).se;
}

// build dfs path, depth
int cnt = 0;
void dfs(int curr, int d){
    idx[curr] = cnt;

    path[cnt++] = ii(d,curr);
    for (vit it = adjList[curr].begin(); it != adjList[curr].end(); it++) {
        dfs(*it,d+1);

        path[cnt++] = ii(d,curr);
    }
}

int N, M, Q, v;

int main(){

    scanf("%d",&N);
    for (int u = 0; u < N; u++){
        scanf("%d",&M);
        for (int i = 0; i < M; i++){
            scanf("%d",&v);
            adjList[u].push_back(v);
        }
    }

    // rooted as 0
    dfs(0,0);
    build(cnt);

    scanf("%d",&Q);
    for (int i = 0, u, v, l, r; i < Q; i++){
    scanf("%d%d",&u,&v);

        l = idx[u], r = idx[v]; if (l > r) swap(l,r);

        printf("%d\n",RMQ(l,r+1));
    }

    return 0;
}

Measured memory_bytes: 44572
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep2(i, a, n) for(ll i = a; i < (ll)(n); i++)
#define memi cout << endl
#define kono(n) cout << fixed << setprecision(n)
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define hina cout << ' '
#define in(n) cin >> n
#define in2(n, m) cin >> n >> m
#define in3(n, m, l) cin >> n >> m >> l
#define out(n) cout << n
const ll mei = (ll)1e9 + 7;

int main(){
  ll a, b, c;
  in3(a, b, c);
  if(a >= c || b >= c){
    out("No");
    memi;
    return 0;
  }
  if(4 * a * b < (c - a - b) * (c - a - b))
    out("Yes");
  else
    out("No");
  memi;
}

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

using namespace std;
using ll = long long;
constexpr ll mod = 1e9+7;
constexpr ll md = mod;
constexpr ll inf = 1e15;
int main(){
    string str;
    cin>>str;
    bool ng = false;
    for(int i=0;i<3;++i){
        if(str[i] == str[i+1]) ng = true;
    }
    if(ng) cout << "Bad" << endl;
    else cout << "Good" << endl;
    return 0;
}



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

using namespace std;

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

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll X;
    cin >> X;
    ll ans = (X / 11LL) * 2LL;
    X %= 11LL;
    if (X > 0) {
        ans++;
        X -= 6;
    }
    if (X > 0) {
        ans++;
        X -= 5;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
p = list(map(int,input().split()))
ans = 0
cou = 0
for i in range(n):
    if p[i] == i+1:
        cou += 1
    elif p[i] != i+1:
        ans += -(-cou//2)
        cou = 0

ans += -(-cou//2)
print(ans)

Measured memory_bytes: 13880
#
import sys
sys.setrecursionlimit(12345678)
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def main():
    n = int(input())
    dl = list(map(int, input().split()))
    ans = 0
    for i in range(n-1):
        for j in range(i + 1, n):
            ans += dl[i] * dl[j]
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 39024
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

vector<vector<P>> G;
vl height;
bool ok = true;

void dfs(ll v, ll h = 0) {
    // 行きの処理はこのへんに書く
    if(height[v] == INF) {
        height[v] = h;
    }
    else {
        if(height[v] != h) {
            ok = false;
        }
        return;
    }
    for(auto p : G[v]) { 
        ll u = p.first;
        ll cost = p.second;
        dfs(u, h + cost);
        // 帰りの処理はこのへんに書く
    }
}

int main() {
    ll n, m;
    cin >> n >> m;    
    
    G.resize(n);  // 辺の重みがすべて0以上のグラフ
    rep(i, m) {
        ll a, b, c;
        cin >> a >> b >> c;
        a--;  b--;
        G[a].pb(make_pair(b, c));
        G[b].pb(make_pair(a, -c));
    }
    
    height.assign(n, INF);
    rep(v, n) {
        if(height[v] == INF) {
            dfs(v);
        }
    }
    
    if(ok) {
        out("Yes");
    }
    else {
        out("No");
    }

    re0;
}

Measured memory_bytes: 15488
N, W = map(int, input().split())
WV = [list(map(int, input().split())) for _ in range(N)]

INF = 10 ** 12
MAX_V = 10 ** 5 + 10
dp = [INF] * MAX_V
dp[0] = 0

for w, v in WV:
	for i in range(MAX_V - 1, v - 1, -1):
		dp[i] = min(dp[i], dp[i - v] + w)
	#print(dp)

max_v = 0
for v, w in enumerate(dp):
	if w <= W:
		max_v = max(max_v, v)
print(max_v)


Measured memory_bytes: 41820
#include <bits/stdc++.h>
using namespace std;
template<class T> class fenwick{
  vector<T> data;
  int size;
public:
  T range(int l, int r);
  T get(int k);
  void add(int i, T val);
  void init(int n);
};

int main(){
  int n;
  string s;
  cin>>n>>s;
  fenwick<int> tree[26];
  for(int i = 0; i < 26; ++i){
    tree[i].init(n);
  }
  for(int i = 0; i < n; ++i){
    tree[s[i]-'a'].add(i, 1);
  }
  int q;
  cin>>q;
  while(q){
    int TYPE;
    cin>>TYPE;
    if(TYPE==1){
      int i;
      char c;
      cin>>i>>c;
      i--;
      if(s[i]!=c){
	tree[s[i]-'a'].add(i,-1); // l at location i remove.
	s[i] = c;
	tree[s[i]-'a'].add(i, 1); // x at location i add.
      }
    }
    else{
      int l, r;
      cin>>l>>r;
      l--, r--;
      int res = 0;
      for(int i = 0; i < 26; ++i){
	if(tree[i].range(l, r)){
	  res++;
	}
      }
      cout<<res<<endl;
    }
    q--;
  }
  return 0;
}
template<class T>void fenwick<T>::init(int n){
  size = n;
  data.resize(size, 0);
}
template<class T>void fenwick<T>::add(int k, T val){
  while(k < size){
    data[k] += val;
    k |= k + 1;
  }
}
template<class T>T fenwick<T>::get(int k){
  T res = 0;
  while(k >= 0){
    res += data[k];
    k = (k&(k+1))-1;
  }
  return res;
}
template<class T>T fenwick<T>::range(int l, int r){
  if(r == -1)r = size - 1;
  return get(r) - get(l - 1);
}


Measured memory_bytes: 53764
#include<iostream>

using namespace std;

int main(){

	int H,W;
	bool flag= true;
	cin>>H>>W;
	if(H==0&&W==0){
			flag = false;
		}
	while(flag==true){
		for(int i=1;i<=H;i++){
			for(int j=1;j<=W;j++){
				cout<<"#";
					if(1<i&&i<H&&0<j&&j<W){
						for(int k=1;k<W-1;k++){
							cout<<".";
							j=W-1;
						}
					}
			}
		cout<<endl;
		
		}
		cin>>H>>W;
		if(H==0&&W==0){
			flag = false;
		}
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 1152
h,w,k = map(int,input().split())
board = [[True if x == '#' else False for x in input()] for i in range(h)]
count = 0
ansBoard = [[0 for j in range(w)] for i in range(h)]
for i in range(h):
    for j in range(w):
        if board[i][j]:
            count += 1
            ansBoard[i][j] = count
        else:
            if j > 0:
                ansBoard[i][j] = ansBoard[i][j-1]
for i in range(h):
    for j in reversed(range(w-1)):
        if ansBoard[i][j] == 0:
            ansBoard[i][j] = ansBoard[i][j+1]
for i in range(1,h):
    if ansBoard[i][0] == 0:
        for j in range(w):
            ansBoard[i][j] = ansBoard[i-1][j]
for i in reversed(range(h-1)):
    if ansBoard[i][0] == 0:
        for j in range(w):
            ansBoard[i][j] = ansBoard[i+1][j]
for b in ansBoard:
    s = ''
    for c in b:
        s += str(c)+' '
    print(s[:-1])

Measured memory_bytes: 7796
#include<bits/stdc++.h>
using namespace std;
#define forr(i,a,n)     for(long long int i=a; i<n; i++)
#define loop(i,a,n)     for(long long int i=a; i>=n; i--) 

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

	long long int a,b,c,d;
	cin>>a>>b>>c>>d;
	cout<<max({a*c, a*d, b*c, b*d});
		
	return 0;
}

Measured memory_bytes: 3624
from collections import Counter
N = int(input())
S = list(map(int,input().split()))
#N = 18
#S = list(range(1,2**N+1))

def solve():
    global S
    S += [0]
    count = Counter(S)
    S = sorted(S)
    T = sorted(list(set(S)))
    M = len(T)
    pre = {T[i]:T[i-1] if i > 0 else 0 for i in range(M)}

    l = [S[-1]]
    count[S[-1]] -= 1

    while len(l) < 2**N:
        for n in l[:]:
            m = pre[n]
            pl = []
            while count[m] == 0:
                pl.append(m)
                m = pre[m]
            if pl:
                pre[n] = m
                for p in pl:
                    pre[p] = m
            if m == 0:
                print('No')
                exit()
            l.append(m)
            count[m] -= 1

    print('Yes')
    #print(count)

solve()


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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

signed main(){
    string a,b,c;
    cin>>a>>b>>c;
    cout<<a[0]<<b[1]<<c[2]<<endl;
    return 0;
}


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

int main() {
  ll n,sum=0;
  cin >> n;
  vector<ll> a(n),b(n),c(n),d(n),e(n);
  r(i,n)cin >>a[i];
  r(i,n)cin >>b[i];
  r(i,n)cin >> c[i];
  sort(a.begin(),a.end());
  sort(b.begin(),b.end());
  sort(c.begin(),c.end());
  
  ll k=n-1;
  for(int i = n-1; i>=0;i--){
    while(b[i]<=a[k]&&k>=0)k--;
    if(k>=0)d[i]=k+1;
    else d[i]=0;
  }
  r(i,n-1)d[i+1]+=d[i];
  k = n-1;
  for(int i = n-1;i>=0;i--){
    while(c[i]<=b[k]&&k>=0)k--;
    if(k>=0)e[i]=k+1;
    else e[i]=0;
  }
  r(i,n){
    if(e[i]>0){
      sum+=d[e[i]-1];
    }
  }
  cout<<sum<<endl;
}

Measured memory_bytes: 4224
#include<stdio.h>
#include<math.h>

struct Point { double x, y;};

void koch( int n, Point a, Point b ){
    if ( n == 0 ) return ;
    Point s, t, u;
    double th = M_PI * 60.0 / 180.0;
    
    s.x = ( 2.0 * a.x + 1.0 * b.x) / 3.0;
    s.y = ( 2.0 * a.y + 1.0 * b.y) / 3.0;
    t.x = ( 1.0 * a.x + 2.0 * b.x) / 3.0;
    t.y = ( 1.0 * a.y + 2.0 * b.y) / 3.0;
    u.x = (t.x - s.x) * cos(th) - (t.y - s.y) * sin(th) + s.x;
    u.y = (t.x - s.x) * sin(th) + (t.y - s.y) * cos(th) + s.y;
    
    koch(n - 1, a, s);
    printf("%.8f %.8f\n", s.x, s.y);
    koch(n - 1, s, u);
    printf("%.8f %.8f\n", u.x, u.y);
    koch(n - 1, u, t);
    printf("%.8f %.8f\n", t.x, t.y);
    koch(n - 1, t, b);
}

int main(){
    Point a, b;
    int n;
    
    scanf("%d", &n);
    
    a.x = 0;
    a.y = 0;
    b.x = 100;
    b.y = 0;
    
    printf("%.8f %.8f\n", a.x, a.y);
    koch(n, a, b);
    printf("%.8f %.8f\n", b.x, b.y);
    
    return 0;
}


Measured memory_bytes: 2668
from collections import deque
H,W = map(int, input().split())
lst1 = [list(input()) for i in range(H) ] #迷路データ。２次元リストで格納し、"."と"#"(壁)からなる


def dfs(maze, visited, sh, sw):
    stack = deque([[sh, sw, 0]])
    visited[sh][sw] = 1
    while stack:
        h, w, t = stack.pop()
        if h == H-1 and w == W-1: #ゴールにたどりつけるなら
            return
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]): #4近傍について探索
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
               new_w < 0 or new_w >= W: #リスト外でないならelif条件へ
                continue
            elif maze[new_h][new_w] != "." and \
                visited[new_h][new_w] == 0: #行ったことがないかつ、壁でないなら
                visited[new_h][new_w] = 1
                stack.append([new_h, new_w, t+1])
    

visited = [[0]*W for _ in range(H)]
dfs(lst1, visited, 0, 0)

flag = 1
for i in range(H):
    for j in range(W):
        if not ((lst1[i][j] == "." and visited[i][j] == 0) \
        or (lst1[i][j] == "#" and visited[i][j] == 1)):
            flag = 0
            break
res = 0
for i in lst1:
    res += i.count("#")

if flag and res == H+W-1:
    print("Possible")
else:
    print("Impossible")
        


Measured memory_bytes: 65112
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n;i++)
using namespace std;
#define mp make_pair
int main(){
    int h,w;
    cin>>h>>w;
    int n; cin>>n;
    vector<int
    >v(n); rep(i,n)cin>>v[i];
    using pii = pair<int, int>;
    pii crt=pii(0,0);
    vector<vector<int>>graph(h,vector<int>(w));
    bool go=true;
    rep(i,n){
        rep(j,v[i]){
            graph[crt.second][crt.first]=i+1;
            if(go&&crt.first<w-1){crt=mp(crt.first+1,crt.second); continue;}
            if(go==false&&crt.first>0){crt=mp(crt.first-1,crt.second); continue;}
            if(go&&crt.first==w-1){go=false;crt.second+=1;continue;}
            if(go==false&&crt.first==0){go=true;crt.second+=1; continue;}
        }
    }
    rep(i,h){
        rep(j,w){
            if(j)cout<<" ";
            cout<<graph[i][j];
        }
        cout<<endl;
    }
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
void debug() {cout<<endl;}
template<typename T,typename... Args>
void debug(T x,Args... args) {cout<<x<<" ";debug(args...);}
#define forn(i,a,b) for(int i=a;i<b;++i)
#define SZ(x) int(x.size())
#define pb push_back
#define F first
#define S second
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;

const ll inf = 1e18;
ll n, s;

bool check(ll b) {
    ll aux = n, sum = 0;
    while (aux) {
        sum += aux % b;
        aux /= b;
    }
    return sum == s;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    cin >> n >> s;
    
    if (n == s) {
        cout << n+1 << endl;
        return 0;
    }
    
    ll ans = inf;
    
    for (ll b = 2; b <= n/b; ++b) {
        if (check(b)) {
            ans = b;
            break;
        }
    }
    
    for (ll d = 1; d <= (n-s)/d; ++d) {
        if ((n-s) % d == 0) {
            ll b = d + 1;
            if (check(b)) ans = min(ans, b);
            b = (n-s)/d + 1;
            if (check(b)) ans = min(ans, b);
        }
    }
    
    if (ans == inf) cout << "-1\n";
    else cout << ans << endl;
}


Measured memory_bytes: 3664
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
using namespace std;

int main()
{
	int N, T;
	cin >> N >> T;
	vector<int> c(N), t(N);
	for (int i = 0; i < N; i++)
		cin >> c[i] >> t[i];
	int ans = 1001;
	int tAns = T + 1;
	for (int i = 0; i < N; i++)
	{
		if (t[i] <= T)
		{
			ans = min(ans, c[i]);
			tAns = t[i];
		}
	}
	if (tAns > T)
		cout << "TLE" << endl;
	else
		cout << ans << endl;
	return 0;
}

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

typedef long long ll;

int X, Y, A, B, C;
vector<int> R, G, W;
vector<int> temp1, temp2;

void input_init(void) {
	cin >> X >> Y >> A >> B >> C;
	R.resize(A);
	for (int i = 0; i < A; ++i)
		cin >> R[i];
	G.resize(B);
	for (int i = 0; i < B; ++i)
		cin >> G[i];
	W.resize(C);
	for (int i = 0; i < C; ++i)
		cin >> W[i];
	sort(R.begin(), R.end());
	sort(G.begin(), G.end());
	sort(W.begin(), W.end());
}

ll solve(void) {
	merge(R.end() - X, R.end(), G.end() - Y, G.end(), back_inserter(temp1));
	merge(temp1.begin(), temp1.end(), W.begin(), W.end(), back_inserter(temp2));
	ll sum = accumulate(temp2.end() - X - Y, temp2.end(), (ll)0);
	return sum;
}

int main(void) {
	input_init();
	ll ans = solve();
	cout << ans << '\n';
	return 0;
}


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

typedef long long ll;
#define int ll
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

#define int ll

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define ALL(s) (s).begin(),(s).end()
#define ALLn(s,n) s,s+n
#define F first
#define S second
#define pb push_back
#define tc(t) int t; cin >> t; while(t--)
#define _ ios_base::sync_with_stdio(false); cin.tie(NULL);
#define D1(x) { cerr << " [" << #x << ": " << x << "]\n"; }
#define D2(x) { cerr << " [" << #x << ": "; for(auto it:x) cerr << it << " "; cerr << "]\n"; }

const ll MOD = 1e9 + 7;
const ll MAXN = 1e6 + 7;
const ll INF = LONG_LONG_MAX;

void solve() {
	int d, t, s;
	cin >> d >> t >> s;

	if (t * s >= d) cout << "Yes";
	else cout << "No";
}

int32_t main() {
	_

#ifndef ONLINE_JUDGE
	freopen("in", "r", stdin);
	freopen("out", "w", stdout);
#endif

	// tc(t)
	solve();
	cerr << "[ Time : " << (float)clock() / CLOCKS_PER_SEC << " secs ]" << endl;
}



Measured memory_bytes: 3744
/* Great things never come from comfort zones,
"whatever the mind of a man can conceive and believe,it can achieve." */
 
#include <bits/stdc++.h>
#define ll long long
#define scf(n) scanf("%d",&n)
#define lscf(n) scanf("%lld",&n)
#define lpri(n) printf("%lld ",n)
#define pri(n) printf("%d ",(int)n)
#define prin(n) printf("%d\n",(int)n)
#define lprin(n) printf("%lld\n",n)
#define rep(i,ini,n) for(int i=ini;i<(int)n;i++)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x)     x.begin(),x.end()
#define tc   int tt; scf(tt); while(tt--)
#define inf INT_MAX
#define ninf INT_MIN
#define gcd __gcd
#define bitcount(n) __builtin_popcount(n)
typedef double dd;
using namespace std;
const ll M =1e9+7;
const int N = 1e5+7;



void my_dbg() { cout << endl; }
template<typename Arg, typename... Args> void my_dbg(Arg A, Args... B) 
{ cout << ' ' << A; my_dbg(B...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", my_dbg(__VA_ARGS__)

    
int main()
{
    int n,f=0,c1=0,c2=0;
    scf(n);
    
    string s;
    cin>>s;
    
    rep(i,0,n-1)
    {
        if(s[i]=='W'&&s[i+1]=='R')
        {f=1;
        break;}
    }
    
    if(f==0)
    prin(f);
    
    else
    {
        f=0;

        rep(i,0,n)
        s[i]=='W'?c2++:c1++;
        
    
        int l=c2,ans=0;
        
        for(int i=n-1;i>n-1-c2;i--)
        if(s[i]=='W')
        l--;
        
        
        ans=min({c1,c2,l});
        
        prin(ans);
    
    }
    
}
  

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

#define MOD 998244353 
#define MAX 310
#define int long long

int power(int x, int n){
  int ans = 1;
  
  while(n){
    if(n&1) ans *= x;
    n >>= 1;
    x *= x;
    x %= MOD;
    ans %= MOD;
  }

  return ans;
}

signed main(){
  static int a[MAX],hoge[MAX][MAX*MAX], hoge2[MAX][MAX*MAX];
  int N, sum = 0, max_ = 0, fuga, temp;
  int ans = 0;
  cin>>N;

  for(int i = 0; i < N; i++){
    cin>>a[i];
    sum += a[i], sum %= MOD;
    max_ = max(max_, a[i]);
  }

  fuga = power(3,N);
  
  hoge[0][0] = 1;
  hoge2[0][0] = 1;

  for(int i = 0; i < N; i++){
    for(int j = 0; j <= sum; j++){
      hoge[i+1][j+a[i]] += hoge[i][j]%MOD;
      hoge[i+1][j] += hoge[i][j]*2%MOD;
      hoge[i+1][j] %= MOD;
      
      hoge2[i+1][j+a[i]] += hoge2[i][j]%MOD;
      hoge2[i+1][j] += hoge2[i][j]%MOD;
      hoge2[i+1][j] %= MOD;
    }
  }
  /*
  for(int j = 0; j <= max_*max_; j++){
    cout<<j<<" "<<hoge[N][j]<<endl;
  }
  */

  for(int i = (sum+1)/2; i <= sum; i++){
    ans += hoge[N][i]*3;
    ans %= MOD;
  }

  if(sum%2 == 0){
    ans = (ans+MOD-hoge2[N][sum/2]*3%MOD)%MOD;
  }

  // cout<<"3^N = "<<fuga<<endl;
  //cout<<ans<<" "<<sum<<endl;

  ans = (fuga - ans + MOD)%MOD;
  
  cout<<ans%MOD<<endl;
  
  return 0;
}


Measured memory_bytes: 454144
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <string>
#define mem(i,a) memset(i,a,sizeof(i))
#define PI acos(-1.0)
#define DMAX 100005
#define MOD 20190823
#define eps 1e-8
#define mp make_pair
#define INF 1e17
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
template<class T> inline void read(T &f){
	f=0;
    T x=1;
    char ch=getchar();
    while(ch<48 || ch>57) {
        if(ch=='-') {
            x=-1;
        }
        ch=getchar();
    }
    while(ch<=57 && ch>=48) {
        f=f*10+ch-'0';
        ch=getchar();
    }
    f*=x;
}
ll x;
ll minn=INF;
int main(){
	ll n;
	read(n);
	for(ll i=1;i<=5;i++){
		read(x);
		minn=min(minn,x);
	}
	ll p=n/minn;
	if(n%minn==0){
		p--;
	}
	cout<<p+5<<endl;
	return 0;
}

Measured memory_bytes: 256
a, b, k = map(int, input().split())

takahashi = a
aoki = b

if(a<k):
    takahashi = 0
    if(b<k-a):
        aoki = 0
    else:
        aoki = a+b-k
else:
    takahashi = a-k
print(takahashi, aoki)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define ri register int
typedef long long ll; 
#define rll register ll
namespace io {
	const int SIZE = (1 << 21) + 1;
	char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int f, qr;
	// getchar
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	// print the remaining part
	inline void flush () {
		fwrite (obuf, 1, oS - obuf, stdout);
		oS = obuf;
	}
	// putchar
	inline void putc (char x) {
		*oS ++ = x;
		if (oS == oT) flush ();
	}
	// input a signed integer
	template <class I>
	inline void gi (I &x) {
		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
		for (x = 0; c <= '9' && c >= '0'; c = gc()) x = (x << 1) + (x << 3) + (c & 15); x *= f;
	}
	// input a letter
	template <class I>
	inline void get (I &x) {
		for (c = gc(); c < 'A' || c > 'Z'; c = gc()) ;
		x = c;
	}
	// input a string
	inline void read (char *s){
		for(c = gc(); c < 'A' || c > 'Z'; c = gc()) ;
		for(; c >= 'A' && c <= 'Z'; c = gc()) *++s = c;
		*++s = '\0';
	}
	// print a signed integer
	template <class I>
	inline void print (I x) {
		if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
		while (x) qu[++ qr] = x % 10 + '0',  x /= 10;
		while (qr) putc (qu[qr --]);
	}
	//no need to call flush at the end manually!
	struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: gi;
using io :: get;
using io :: read;
using io :: putc;
using io :: print;
const int N=5005;
const ll inf=1e18;
struct segtree{
	ll mn[N<<2],tag[N<<2];
	#define lc x<<1
	#define rc x<<1|1 
	inline void build(ri x,ri l,ri r){
		mn[x]=inf;
		if(l==r)
			return;
		ri mid=l+r>>1;
		build(lc,l,mid);
		build(rc,mid+1,r);
	}
	inline void up(ri x){
		mn[x]=min(mn[lc],mn[rc])+tag[x];
	}
	inline void upd(ri x,ri l,ri r,ri p,rll v){
		v-=tag[x];
		if(l==r){
			mn[x]=v+tag[x];
			return;
		}
		ri mid=l+r>>1;
		p<=mid?upd(lc,l,mid,p,v):upd(rc,mid+1,r,p,v);
		up(x);
	}
	inline void modify(ri x,ri l,ri r,ri ql,ri qr,rll v){
		if(ql<=l&&r<=qr){
			mn[x]+=v;
			tag[x]+=v; 
			return;
		}
		ri mid=l+r>>1;
		if(ql<=mid) modify(lc,l,mid,ql,qr,v);
		if(qr> mid) modify(rc,mid+1,r,ql,qr,v);
		up(x);
	}
	inline ll query(ri x,ri l,ri r,ri ql,ri qr){
		if(ql<=l&&r<=qr)
			return mn[x];
		ri mid=l+r>>1;
		rll v=inf;
		if(ql<=mid) v=		query(lc,l,mid,ql,qr);
		if(qr> mid) v=min(v,query(rc,mid+1,r,ql,qr));
		v+=tag[x];
		return v;
	}
}seg;
int p[N];
ll dp[N];
int main(){
	ri n,A,B,C,i,j;
	gi(n);gi(A);gi(B);
	C=B-A;
	for(i=1;i<=n;++i) gi(p[i]);
	p[n+1]=n+1;
	seg.build(1,0,n+1);
	seg.upd(1,0,n+1,0,0);
	for(i=1;i<=n+1;++i)
		dp[i]=seg.query(1,0,n,0,p[i]-1)+(ll)A*(i-1),
		seg.upd(1,0,n+1,p[i],dp[i]-(ll)A*i),
		seg.modify(1,0,n+1,p[i]+1,n+1,C);
	printf("%lld\n",dp[n+1]);
	return 0;
}

Measured memory_bytes: 2560
import java.util.*;
import java.lang.String;

public class Main {

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

        String vStr = sc.nextLine();
        Map<Integer, Integer> vList = str2List(vStr);

        int n = vList.get(0);
        int k = vList.get(1);

        String s = sc.nextLine();
        String sArr[] = s.split("");

        switch (sArr[k-1]) {
            case "A":
                sArr[k-1] = "a";
                break;
            case "B":
                sArr[k-1] = "b";
                break;
            case "C":
                sArr[k-1] = "c";
                break;
        }

        for (int i = 0; i < n; i++) {
            System.out.print(sArr[i]);
        }
    }

    static Map<Integer, Integer> str2List(String str) {
        String[] vArrStr = str.split(" ");

        Map<Integer, Integer> ret = new HashMap<>();
        Integer key = 0;
        for (String val:vArrStr) {
            ret.put(key, Integer.valueOf(val));
            key++;
        }

        return ret;
    }
}


Measured memory_bytes: 23252
#include "bits/stdc++.h"
using namespace std;

int main() {
	int n;
	cin >> n;
	map<int, int> mpd;
	for (int i = 0; i < n; i++) {
		int d;
		cin >> d;
		mpd[d]++;
	}
	
	int m;
	cin >> m;
	map<int, int> mpt;
	vector<int> vec(m);
	for (int i = 0; i < m; i++) {
		cin >> vec.at(i);
		mpt[vec.at(i)]++;
	}
	for (int i = 0; i < m; i++) {
		if (mpt[vec.at(i)] > mpd[vec.at(i)]) {
			cout << "NO" << endl;
			return 0;
		}
	}
	cout << "YES" << endl;
}


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

int main() {
  int N;
  cin >> N;
  vector<int>vec(N);
  for(int i=0;i<vec.size();i++) {
    cin >> vec.at(i);
  }
  sort(vec.begin(),vec.end());
  reverse(vec.begin(),vec.end());
  
  int Alice=0;
  int Bob=0;
  
  if(N%2==0) {
    for(int i=0;i<vec.size()-1;i+=2) {
      Alice+=vec.at(i);
      Bob+=vec.at(i+1);
    }
    cout << Alice-Bob << endl;
  }
  
  else {
     for(int i=0;i<vec.size()-2;i+=2) {
      Alice+=vec.at(i);
      Bob+=vec.at(i+1);
    }
    Alice+=vec.at(N-1);
    cout << Alice-Bob << endl;
  }
}

Measured memory_bytes: 256
// https://atcoder.jp/contests/arc069/tasks/arc069_b
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, a, b) for (int i = (a); i < (int)(b); ++i)

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    s[n] = s[0], s[n + 1] = s[1];
    REP(i, 4) {
        bitset<100005> a;
        a[0] = i & 1, a[1] = (i >> 1) & 1;
        FOR(j, 2, n + 2) a[j] = (s[j - 1] == 'x') ^ a[j - 1] ^ a[j - 2];
        if (a[0] == a[n] && a[1] == a[n + 1]) {
            REP(j, n) cout << (a[j] ? "W" : "S");
            cout << "\n";
            return 0;
        }
    }
    cout << "-1\n";
    return 0;
}


Measured memory_bytes: 592