akhauriyash/Code-Regression huggingface dataset:
open System

let cs : char list list = ["dream";"dreamer";"erase";"eraser"] |> List.map (fun x -> x.ToCharArray() |> Array.rev |> Array.toList)
let s : char list = Console.ReadLine().ToCharArray() |> Array.rev |> Array.toList

let pre_match a b =
    try
        let sub = List.take (List.length a) b
        a = sub
    with
        | _ -> false


let rec f str = 
    if List.isEmpty str then true 
    else
        let ls=[ for c in cs do
                    if pre_match c str then
                        yield f (List.skip (List.length c) str) ]
        if List.exists (fun x -> x) ls then true else false

printfn "%s" (if f s then "YES" else "NO")


Measured memory_bytes: 48148
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define int ll
#define pb push_back
#define setbits(x)          __builtin_popcountll(x)
#define endl "\n"
typedef long long ll;

int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
    cin>>arr[i];
map<int,int> mp;
int ans=0;
for(int i=0;i<n;i++)
{
    int val=arr[i]-i;
    ans+=mp[val];
    mp[-(arr[i]+i)]++;
}
cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 27952
#include<iostream>
#include<string>
#include<set> 
using namespace std;
int main()
{
	set<int >s;
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int t;
		cin>>t;
		s.insert(t);
	}
	cout<<s.size();
} 

Measured memory_bytes: 256
fun main(args: Array<String>) {
  var tmp = readLine()!!.split(" ").map(String::toLong);
  val a = tmp[0];
  val b = tmp[1];
  val c = tmp[2];
  val t = c - a - b
  if (t <= 0) {
    println("No")
  } else {
    println(if(4 * a * b < t * t) "Yes" else "No")
  }
}


Measured memory_bytes: 37868
#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;

// 入力
long long a,b,c,d;
long long p,q,r;
long long mod=998244353;

long long dp[3001][3001][2];

int main() {
  cin >> a >> b >>c >>d;


  dp[a][b][0]=1;
  for (int j= b+1; j <=d; ++j){
      
      dp[a][j][0]=dp[a][j-1][0]*a%mod;
  }
  // DPループ
  for (int i = a+1; i <=c; ++i) {
    
    p=dp[i-1][b][0]*b%mod;
    
    dp[i][b][0]=p;
    dp[i][b][1]=p;

    for (int j = b+1; j<=d+1; ++j) {
        dp[i][j][0]=(( dp[i-1][j][0]*j)%mod+  ((dp[i][j-1][0]-dp[i][j-1][1])*i + dp[i][j-1][1] ))%mod;
        dp[i][j][1]=(dp[i-1][j][0]*j) %mod;
    }
  }

  cout << (dp[c][d][0]+mod)%mod << endl;
}


Measured memory_bytes: 144080
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long u_ll;
typedef pair<int, int> pair_;
 
const int INF = 1001001001;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
int k;
 
 
int main(){
   
    vector<char> a(3);
    bool ans = false;
    rep(i, 3) {
        cin >> a[i];
    }
    rep(i, 3) if(a[i] == '7') ans = true;
    if(ans) cout << "Yes";
    else cout << "No";
    return 0;
}

Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
 //freopen("input.txt", "r", stdin); 
 //freopen("output.txt", "w", stdout); 

int a;
cin>>a;
cout<<(a + a*a + a*a*a);
return 0;
}

Measured memory_bytes: 3568
#include <iostream>
using namespace std;
int main()
{
	int a,b;
	long long ans;
	cin>>a>>b;
	for (int i=0;i<b;i++)
	{
		int x;
		cin>>x;
		ans+=x;
	}
	if (ans>=a) cout<<"Yes";
	else cout<<"No";
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-2;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
int n;
int x[16], y[16];
bool used[1 << 16];
int ans[1 << 16];
char t[4][4];
int dfs(int s) {
	if (s == 0)return 0;
	if (used[s])return ans[s];
	used[s] = true;
	int mp[4][4] = {};
	rep(j, 16) {
		if (s&(1 << j)) {
			mp[j / 4][j % 4] = 1;
		}
	}
	int ret = mod;
	rep(i, 16) {
		for (int j = -3; j <= 3; j++) {
			for (int k = -3; k <= 3; k++) {

				int cs = s;
				char u = '?'; bool valid = true;
				for (int l1 = j; l1 < j + x[i]; l1++) {
					if (l1 < 0 || l1 >= 4)continue;
					for (int l2 = k; l2 < k + y[i]; l2++) {
						if (l2 < 0 || l2 >= 4)continue;
						if (!mp[l1][l2])continue;
						if (u == '?')u = t[l1][l2];
						else if (u != t[l1][l2])valid = false;
						int z = l1 * 4 + l2;
						cs ^= (1<<z);
					}
				}
				if (!valid)continue;
				if (s == cs)continue;
				ret = min(ret, dfs(cs));
			}
		}
	}
	return ans[s] = ret + 1;
}
int main() {
	cin >> n;
	rep(i, n) {
		cin >> x[i] >> y[i];
	}
	rep(i, 4) {
		rep(j, 4) {
			cin >> t[i][j];
		}
	}
	cout << dfs(65535) << endl;
	//cout << ans[65535] << endl;
	//stop
	return 0;
}



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

int main(){
		
		int n,k;
		cin>>n>>k;
		
		int arr[n+1] = {};
		
		for(int i=0;i<k;i++){
				int d;
				cin>>d;
				int temp;
				for(int j=0;j<d;j++){
					cin>>temp;
					arr[temp] = 1;
				}
		}
		
		int count = 0;
		
		for(int i=1;i<=n;i++)
		{
			if(arr[i] == 0)
				count++;
		}
		cout<<count<<endl;
		return 0;
}




Measured memory_bytes: 3596
#include <iostream>
#include <cstdio>
#define rep(i,n) for(long i=0; i<(n); i++)
#define dmp(x) cerr << #x << " = " << x << endl;
using namespace std;

bool m[100009];
long a[100009];
char c[100009];
long d[100009];

long long calc(int n)
{
  if(m[n])
    return n;
  else
    return calc(a[n]);
}

int main()
{
  int N,Q;
  while(scanf("%d %d", &N, &Q),N+Q){
    for(int i=2;i<N+1;i++)
      scanf("%ld",a+i);
    rep(i,N+2) m[i]=false;
    m[1]=true;
    rep(i,Q)
      scanf(" %c %ld", c+i,d+i);
    
    long long ret=0;
    
    rep(i,Q) switch(c[i]) {
    case 'M':
      m[d[i]]=true;
      break;
    case 'Q':
      ret += calc(d[i]);
      break;
    }
    printf("%lld\n", ret);
  }
}

Measured memory_bytes: 1856
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define uint unsigned int
#define ull  unsigned long long
typedef string str;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef map<int, int> mii;
typedef vector<int> vi;
typedef vector<bool> vb;
#define pb push_back
#define fi first
#define se second
#define in insert
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
const int INF = 1e9 + 5;
const int N = 2e5 + 123;
int main(){
    speed;
    int n;
    cin >> n;
    map<str, int> m;
    m["AC"];
    m["WA"];
    m["TLE"];
    m["RE"];
    for(int i = 0; i < n; ++i){
        str s;
        cin >> s;
        m[s]++;
    }
    cout << "AC x " << m["AC"] << "\n";
    cout << "WA x " << m["WA"] << "\n";
    cout << "TLE x " << m["TLE"] << "\n";
    cout << "RE x " << m["RE"] << "\n";
}

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

int main()
{
    int n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    s[k-1]=tolower(s[k-1]);
    cout<<s<<endl;
    return 0;
}

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

#ifdef _DEBUG
    #include "/home/v-o_o-v/deb.h"
    #define deb(x...)cerr << "[" << #x << "] = [";_print(x);
#else
    #define deb(x...)
#endif

#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m, c;
    cin >> n >> m >> c;
    int b[m];
    for(int i = 0; i < m; i++)cin >> b[i];
    int ans = 0;
    for(int i = 0; i < n; i++){
        int sum = 0;
        for(int j = 0; j < m; j++){
            int x;
            cin >> x;
            sum += (x * b[j]);
        }
        // deb(sum);
        if(sum + c > 0)ans++;
    }
    cout << ans << '\n';
    return 0;
}
// Write Here


Measured memory_bytes: 3672
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ft first
#define sd second
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,c=0;
    cin>>n;
    vector<int> p(n);
    for(auto& i:p) cin>>i;
    fr(i,n-2) c+=((p[i]<p[i+1])&&(p[i+1]<p[i+2]))||((p[i]>p[i+1])&&(p[i+1]>p[i+2]));
    cout<<c<<endl;
}

Measured memory_bytes: 896
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
typedef long double lb;
#define int long long
#define double long double
#define endn "\n"
typedef pair<int,int> P;
template<class T> inline bool chmin(T& a, T b){if(a>b){a = b;return 1;}return 0;}
template<class T> inline bool chmax(T& a, T b){if(a<b){a = b;return 1;}return 0;}
const int MOD = 1000000007;
//const int MOD = 998244353;
const ll INF = 1e16;
const double EPS = 1e-10;
const double PI = 3.141592653589793;
const string abc="abcdefghijklmnopqrstuvwxyz";
const string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 


////////////////////////////////////////////////////////////////////
///////////////////////___modpow___////////////////////
ll modpow(ll a,  ll n, const ll &MOD = MOD){
  ll ret = n == 0 ? 1 : modpow(a, n/2, MOD);
  (ret *= ret) %= MOD;
  if(n%2)((ret *= a) %= MOD);
  return ret;
}
///////////////////////___modinv___////////////////////
ll modinv(ll d, const ll &MOD = MOD){
  return modpow(d, MOD-2, MOD);
}
///////////////////////___combination___////////////////////
vector<ll> fac, finv, inv;
void COMinit(const int MAX = 5000000, const ll &MOD = MOD){
  fac.resize(MAX);finv.resize(MAX);inv.resize(MAX);
  fac[0] = fac[1] = finv[0] = finv[1] = inv[1] = 1;
  repd(i,2,MAX){
    fac[i] = fac[i-1] * i % MOD;
    inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
    finv[i] = finv[i-1] * inv[i] % MOD;
  }
}
ll 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 n;multiset<int> st;
signed main(){
  cin>>n;
  rep(i,n){
    int a;cin>>a;
    auto itr = st.lower_bound(a);
    if(itr != st.begin())st.erase(--itr);
    st.insert(a);
  }
  cout << st.size() << endl;
}



Measured memory_bytes: 4992
function main(input){
    var tmp = input.split('\n');
    var n = parseInt(tmp[0]);
    var s = tmp[1];
    if(n%2==0){
        var t = s.slice(0,n/2) + s.slice(0,n/2);
        if(t==s){
            console.log("Yes");
        }else{
            console.log("No");
        }
    }else{
        console.log("No");
    }
}
main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 21064
#include <iostream>
#include <deque>
#include <cstdint>
#include <string>
#include <algorithm>

typedef std::deque<std::uint64_t> DType;

int main() {
	DType D;
	std::uint64_t N;
	std::uint64_t C;
	std::string S;
	std::cin >> C;

	DType::iterator it = D.begin();

	for (std::size_t i = 0; i < C; i++) {
		if (!(std::cin >> S)) break;
		if (S[0] == 'i' ||S[0] == 'I') {//insert
			std::cin >> N;		
			D.push_front(N);
			continue;
		}
		if (S.size() == 6) {//delete
			std::cin >> N;	
			auto it=std::find(D.begin(), D.end(), N);
			if(it!= D.end())D.erase(it);
			continue;
		}
		if (S.size() == 11) {//deletefirst
			D.pop_front();
			continue;
		}
		if (S.size() == 10) {//deletelast
			D.pop_back();
			continue;
		}
	}

	for (auto it = D.begin(); it != D.end(); it++) {
		if(it!=D.begin())std::cout << ' ';

		std::cout << *it;
	}

	std::cout<<std::endl;

	return 0;
}

Measured memory_bytes: 10960
#include <stdio.h>

int main(void) {
    int A, B, C, D, b;
    scanf("%d%d%d%d", &A, &B, &C, &D);
    while (1) {
        C-=B;
        if (C<=0) {
            b=1;
            break;
        }
        A-=D;
        if (A<=0) {
            b=0;
            break;
        }
    }
    if (b) printf("Yes");
    else printf("No");
    return 0;
}


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

int main() {
  int num1,num2;
  char op;

  cin >> num1 >> op >> num2;

  if (op == '+') {
	cout << num1 + num2 << endl;
  } else if (op == '-') {
	cout << num1 - num2 << endl;
  }  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const ll INF = 1LL << 60;
const ll MOD = (int) 1e9 + 7;

int main(){
    ll n, m;
    cin >> n >> m;
    vector<ll> a;
    for (int i = 0; i < n; i++)
    {
        ll x;
        cin >> x;
        a.push_back(x / 2);
    }
    ll lcm = 1;
    for (int i = 0; i < n; i++)
    {
        ll g = __gcd(lcm, a[i]);
        lcm = lcm * a[i] / g;
    }
    bool flag = true;
    for (int i = 0; i < n; i++)
    {
        if ((lcm / a[i]) % 2 == 0) {
            flag = false;
            break;
        }
    }
    if (!flag) {
        cout << 0 << "\n";
        return 0;
    }
    cout << (m / lcm + 1) / 2 << "\n";
}

Measured memory_bytes: 1400
#include <bits/stdc++.h>
    using namespace std;
     
    int main() {
      int h,w;
      cin >> h >> w;
      vector<string> field(h),ans(h);
      for (int i=0; i<h; i++){
        cin >> field.at(i);
      }
      for (int i=0; i<h; i++){
        string a,b,c,ans;
        b = field.at(i);
        for (int j=0; j<w; j++){
          if (b[j]=='.'){
            int count=0;
            if (i!=0){
              a = field.at(i-1);
              if (j!=0){
                if (a[j-1]=='#') count++;
              }
              if (a[j]=='#') count++;
              if (j!=w){
                if (a[j+1]=='#') count++;
              }
            }
            if (i!=h-1){
              c = field.at(i+1);
              if (j!=0){
                if (c[j-1]=='#') count++;
              }
              if (c[j]=='#') count++;
              if (j!=w){
                if (c[j+1]=='#') count++;
              }
            }
            if(j!=0){
              if(b[j-1]=='#') count++;
            }
            if(j!=w-1){
              if(b[j+1]=='#') count++;
            }
            ans += to_string(count);
          }
          else ans += "#";
        }
        cout << ans << endl;
      }
    }

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

int main()
{
    string S;
    cin >> S;
    if ( S[0]==S[1] && S[1] == S[2])
    {
        cout << "No";
    }
    else
    {
        cout << "Yes";
    }
    return 0;
}

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

using namespace std;


int main() {
	int a = 0, b = 0;
	cin >> a >> b;
	assert(a >= 1 && a <= 100);
	assert(b >= 1 && b <= 100);
	int c = a - (2 * b);
	cout << ((c >= 0)? c : 0) << endl;

	return 0;
}


Measured memory_bytes: 256
A, B, C, X, Y = map(int, input().split(" "))
AB = 2 * C
if AB > A + B:
  case = 1
else:
  case = 2

if case == 1:
  print(A * X + B * Y)
  exit()

if case == 2:
  if X > Y:
    Z = Y
    X = X - Y
    Y = 0
    if AB < A:
      Z = Z + X
      X = 0
  else:
    Z = X
    Y = Y - X
    X = 0
    if AB < B:
      Z = Z + Y
      Y = 0
print(A * X + B * Y + AB * Z) 

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;

int main(){
    string node[6] = {"12","@3","1@","45","52","21"};
    string input;
    while(cin >> input, input != "#"){
        int start = 0;
        bool isPossibble = true;
        for(int i=0; i < input.size(); i++){
            string hoge = input.substr(i,1);
            string city = node[start].substr(atoi(hoge.c_str()), 1);
            if(city == "@"){
                isPossibble = false;
                break;
            }
            start = atoi(city.c_str());
        }
        if(isPossibble && start == 5) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

Measured memory_bytes: 1200
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	sc.Scan()
	iv, _ := strconv.Atoi(sc.Text())
	return iv
}

func init() {
	sc.Split(bufio.ScanWords)
}

func main() {
	n := scanInt()
	xm := make(map[int]bool)
	for i := 0; i < n; i++ {
		a := scanInt()
		xm[a] = true
	}

	if v := len(xm); v%2 == 1 {
		fmt.Println(v)
	} else {
		fmt.Println(v - 1)
	}
}


Measured memory_bytes: 4608
import sys


def is_even_seq(s):
    len_s = len(s)
    if len_s % 2 != 0:
        return False
    left = s[: (len_s // 2)]
    right = s[(len_s // 2) :]

    return left == right


def test():
    assert is_even_seq("abaababaab")


if __name__ == "__main__":
    S = input()
    for i in range(1, len(S) - 1):
        s = S[:-i]
        if is_even_seq(s):
            print(len(s))
            sys.exit(0)

Measured memory_bytes: 3064
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
string S1,S2;
int A1,A2;
int main()
{
	while(true){
	cin >> S1 >> S2;
	A1=0;A2=0;
	if(S1.length()==1)break;
	for(int i=0;i<4;i++){
		if(S1[i]==S2[i])A1++;
	}
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			if(i==j)continue;
			if(S1[i]==S2[j])goto a;
		}
		continue;
		a:;
		A2++;
	}
	printf("%d %d\n",A1,A2);
	}
	return 0;
}

Measured memory_bytes: 1180
import sys
S = input()
def is_palindrome(S):
  P = S[::-1]
  if S == P:
    return True
  return False
if is_palindrome(S):
  N = len(S)
  if is_palindrome(S[0:(N-1)//2]) and is_palindrome(S[(N+3)//2-1:N]):
    print('Yes')
    sys.exit(0)
print('No')

Measured memory_bytes: 3060
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, k; cin >> n >> k;
    vector<int> nums(n);
    for (int &a : nums) {
        cin >> a;
    }

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

    int res = 0;
    for (int i = 0; i < k; ++i) {
        res += nums[i];
    }    
	cout << res << endl;
}


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

void readFromInputFile() {
#ifdef LOCAL
    static std::ifstream in("/Users/hoo/CLionProjects/for_atcoder/input");
    std::cin.rdbuf(in.rdbuf());
#endif
}

int main() {
    readFromInputFile();
    int N,K;
    cin>>N>>K;
    vector<int> a;
    for(int i=0;i<N;i++){
        int t;
        cin>>t;
        a.push_back(t);
    }
    for(int i=0;i<N-K;i++){
        if (a[i]<a[i+K]) {
            cout<<"Yes"<<endl;
        } else {
            cout<<"No"<<endl;
        }
    }

    return 0;
}


Measured memory_bytes: 4244
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); ++ i)
#define rrp(i,a,b) for (int i = (a); i >= (b); -- i)
#define gc() getchar()
#define fir first
#define sec second
typedef pair<int,int> pii;
typedef long double db;
typedef long long ll;
template <typename tp>
inline void read(tp& x) {
  x = 0; char tmp; bool key = 0;
  for (tmp = gc(); !isdigit(tmp); tmp = gc())
    key = (tmp == '-');
  for (; isdigit(tmp); tmp = gc()) 
    x = (x << 3) + (x << 1) + (tmp ^ '0');
  if (key) x = -x;
}
template <typename tp>
inline void ckmn(tp& x,tp y) {
  x = x < y ? x : y;
}
template <typename tp>
inline void ckmx(tp& x,tp y) {
  x = x < y ? y : x;
}

int MOD;
inline void Add(int& x,int y) {
  x = x + y >= MOD ? x + y - MOD : x + y;
}
inline void Sub(int& x,int y) {
  x = x - y < 0 ? x - y + MOD : x - y;
}
int power(int a,int b) {
  int ret = 1;
  while (b) {
    if (b&1) ret = 1ll * ret * a % MOD;
    a = 1ll * a * a % MOD;
    b >>= 1;
  }
  return ret;
}

const int N = 260;
int dp[N * 2][N], n, ans;
pii arr[N << 1];
int calc(int lim) {
  int ret = 0;
  while ((ret + 1) * (ret + 1) <= lim)
    ++ ret;
  return ret;
}
void doit(int num) {
  // j * j <= n * n - i * i - 1
  rep (i, 0, n-1)
    arr[i+1] = pii(calc(n*n - i*i - 1), i);
  rep (i, n, 2 * n - 1)
    arr[i+1] = pii(min(calc(4 * n * n - i * i), 2 * n - 1), i);
  sort(arr + 1, arr + 2 * n + 1, [=](pii a,pii b) -> bool {
      if (a.fir != b.fir) return a.fir < b.fir;
      return a.sec > b.sec;
    });
  memset(dp, 0, sizeof dp);
  dp[0][0] = 1;
  int cur = 0;
  rep (i, 1, 2 * n) {
    if (arr[i].sec >= n) {
      rep (j, 0, n)
	Add(dp[i][j], 1ll * dp[i-1][j] * max(0, (arr[i].fir + 1 - cur - j)) % MOD);
      ++ cur;
    } else {
      int tmp = calc(4 * n * n - arr[i].sec * arr[i].sec); tmp = min(tmp, 2 * n - 1);
      rep (j, 0, n) {
	Add(dp[i][j], 1ll * dp[i-1][j] * max(0, (tmp+1 - n - num - (i-1-cur-j))) % MOD);
	Add(dp[i][j+1], 1ll * dp[i-1][j] * max(0, arr[i].fir+1 - cur - j) % MOD);
      }
    }
  }
  if (num&1) Sub(ans, dp[2*n][num]);
  else Add(ans, dp[2*n][num]);
}
int main() {
  read(n), read(MOD);
  rep (i, 0, n) doit(i);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 768
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;
struct data{ int A, B, O;};
const int MAX = 50001;
const int Row = 0;
const int Col = 1;

bool fin[2][MAX];
int r,c,q;

int main(){
  
  while(cin >> r >> c >> q && r+c+q){
    memset(fin,false,sizeof(fin));
    
    vector<data> V(q);
    
    for(int i = 0; i < q; i++) cin >> V[i].A >> V[i].B >> V[i].O;
    
    int delR = 0, delC = 0;
    long long ans = 0;
    
    for(int i = V.size()-1; i >= 0; i--){

      if(V[i].A){
	// column
	if(fin[Col][V[i].B]) continue;

	if(V[i].O) ans += r-delC;
	  fin[Col][V[i].B] = true;
	  delR++;
	
      }else{
	// row
	if(fin[Row][V[i].B]) continue;

	if(V[i].O)  ans += c-delR;
	  fin[Row][V[i].B] = true;
	  delC++;
      }
    }
    
    cout << ans << endl;
  }
  return 0;
}

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

int main(){
    int N, K;
    cin >> N >> K;

    int count = 0;

    vector<int> h(N);

    for (size_t i = 0; i < N; i++)
    {
        cin >> h.at(i);
    }
    

    for (size_t i = 0; i < N; i++)
    {
        if (h.at(i) >= K)
        {
            count++;
        }
        
    }
    cout << count << endl;
}

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

using namespace std;

struct Min {
	long n;
	Min(long n) :n(n) {}
	operator long() const { return n; }
	void operator+=(const Min &m) { n = min(n, m.n); }
	const Min &operator*(int) const { return *this; }
};
struct seg {
	typedef Min N;
	const N I = 1e9;
	vector<N> t, u;
	seg(int n) :t(n - 1, I), u(n + n - 1, I) {}
	void upd(int a, int b, N n, int p, int q, int l, int r) {
		for (;;) {
			if (b <= l || r <= a)
				break;
			if (a <= l && r <= b) {
				u[q] += n;
				break;
			}
			t[p] += n * (min(b, r) - max(a, l));
			int m = (l + r) / 2;
			upd(a, b, n, p + 1, q + 1, l, m);
			p += m - l;
			q += (m - l) * 2;
			l = m;
		}
	}
	void upd(int a, int b, N n) {
		upd(a, b, n, 0, 0, 0, t.size() + 1);
	}
	N out(int a, int b, int p, int q, int l, int r) const {
		N n = I;
		for (;;) {
			if (b <= l || r <= a)
				break;
			if (a <= l && r <= b) {
				if (l + 1 < r) n += t[p];
				n += u[q] * (r - l);
				break;
			}
			int m = (l + r) / 2;
			n += out(a, b, p + 1, q + 1, l, m);
			p += m - l;
			q += (m - l) * 2;
			l = m;
		}
		return n;
	}
	N out(int a, int b) const {
		return out(a, b, 0, 0, 0, t.size() + 1);
	}
};

int b[222222];
pair<int, int> l[222222];
int main() {
	int n;
	cin >> n;
	int d = n;
	for (int i = 0; i < n; i++)
		scanf("%d", b + i), d -= b[i];
	int q;
	cin >> q;
	for (int i = 0; i < q; i++)
		scanf("%d%d", &l[i].first, &l[i].second);
	sort(l, l + q);
	l[q].first = n + 1;
	seg s(n + 1);
	s.upd(0, 1, d);
	int p = 1;
	for (int i = 0;; i++) {
		for (; p < l[i].first; p++)
			s.upd(p, p + 1, s.out(p - 1, p) + b[p - 1] * 2 - 1);
		if (i == q) break;
		s.upd(l[i].second, l[i].second + 1, s.out(p - 1, l[i].second));
	}
	cout << s.out(n, n + 1) << endl;
	return 0;
}


Measured memory_bytes: 7296
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...)name
#define _rep(i,n)repi(i,0,n)
#define repi(i,a,b)for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x)x
#define rep(...)MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c)c.begin(),c.end()
#define write(x)cout<<(x)<<'\n'
using namespace std; typedef long long ll; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T, class U>bool chmax(T& a, U&& b) { return a < b ? a = b, 1 : 0; }
template<class T, class U>bool chmin(T& a, U&& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

constexpr int dy[4] = { 0,1,0,-1 }, dx[4] = { 1,0,-1,0 };

int N, M, Q;
vector<string> S;
vv<bool> visited;
vv<array<int, 4>> movec;

void dfs(int y, int x) {
    rep(d, 4) {
        int ny = y + dy[d], nx = x + dx[d];
        if (ny == -1 || ny == N || nx == -1 || nx == M || S[ny][nx] != '1' || visited[ny][nx]) continue;
        visited[ny][nx] = true;
        movec[ny + 1][nx + 1][d]++;
        dfs(ny, nx);
    }
}

int main() {
    cin >> N >> M >> Q;
    S.resize(N);
    rep(i, N) cin >> S[i];

    visited = vvec(N, M, false);
    movec = vvec(N + 2, M + 2, array<int, 4>());
    vv<int> startc = vvec(N + 2, M + 2, 0);

    rep(i, N) rep(j, M) {
        if (S[i][j] == '1' && !visited[i][j]) {
            visited[i][j] = true;
            startc[i + 1][j + 1]++;
            dfs(i, j);
        }
    }

    rep(i, 1, N + 1) rep(j, 1, M + 1) {
        movec[i][j][0] += movec[i - 1][j][0];
        movec[i][j][2] += movec[i - 1][j][2];
        movec[i][j][1] += movec[i][j - 1][1];
        movec[i][j][3] += movec[i][j - 1][3];
        startc[i][j] += startc[i - 1][j] + startc[i][j - 1] - startc[i - 1][j - 1];
    }

    vector<int> ans(Q);
    rep(i, Q) {
        int y, x, w, z;
        cin >> y >> x >> w >> z;

        ans[i] = startc[w][z] - startc[w][x - 1] - startc[y - 1][z] + startc[y - 1][x - 1];
        ans[i] += movec[w][x][0] - movec[y - 1][x][0];
        ans[i] += movec[w][z][2] - movec[y - 1][z][2];
        ans[i] += movec[y][z][1] - movec[y][x - 1][1];
        ans[i] += movec[w][z][3] - movec[w][x - 1][3];
    }

    for (int a : ans) write(a);
}

Measured memory_bytes: 87296
#include<bits/stdc++.h>
using namespace std;
string s,t;
int len;
int main()
{
    cin>>s;
    t=s;
    reverse(s.begin(),s.end());
    len=s.length();
    for(int i=0;i<len;++i)
    {
        if(s[i]=='b')
		    s[i]='d';
        else if(s[i]=='d')
		    s[i]='b';
        else if(s[i]=='p')
		    s[i]='q';
        else if(s[i]=='q')
		    s[i]='p';
    }
    if(s==t)
	    printf("Yes");
    else
	    printf("No");
	return 0;
}

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

int main()
{
    int N, K, tmp=0;
    cin >> N >> K;
    vector<int> len(N);

    for (int i = 0; i < N;i++){
        cin>>len.at(i);
    }
    sort(len.begin(), len.end(),std::greater<int>());
    for (int i = 0; i < K;i++){
        tmp = tmp + len.at(i);
    }
    cout << tmp << endl;
}

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> mat;
#define FOR(i,a,b) for(int i=(a);i<(int)(b);++i)
#define rep(i,n) FOR(i,0,n)
#define ALL(x) (x).begin(),(x).end()
#define mset(a,x) memset(a,x,sizeof(a))
#define OUT(x) cout<<(x)<<"\n"
#define SZ(x) (int)(x).size()
#define FASTIO cin.tie(0),ios::sync_with_stdio(0)

ll n, c, k;

int main() {
    FASTIO;
    cin >> n >> c >> k;
    vector<ll> T(n);
    rep(i, n) {
        cin >> T[i];
    }
    sort(ALL(T));

    ll ans = 0;
    rep(i, n) {
        ll tt = T[i] + k;
        int j = i + 1;
        while(j < n && T[j] <= tt && j - i < c) ++j;
        ++ans;
        i = j - 1;
        //OUT(j);
    }

    OUT(ans);

    return 0;
}

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

int main() {
    int N, M; cin >> N >> M;
    vector<int> H(N);
    rep(i,N){
        cin >> H[i];
    }

    Graph G(N);
    rep(i, M){
        int a, b; cin >> a >> b;
        G[a-1].insert(H[b-1]);
        G[b-1].insert(H[a-1]);
    }

    int ans = 0;

    rep(i, N){
        if(G[i].empty()){
            ans++;
        } else {
            if (H[i] > *rbegin(G[i])){
                ans++;
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 17780
# Problem https://atcoder.jp/contests/abc064/tasks/abc064_a
# Python 1st Try
rgbs = list(map(int,input().split(' ')))
g = rgbs[1]
b = rgbs[2]
answer =''
checkgb=((g*10+b)%4)
if checkgb == 0:
    answer = "YES"
else:
    answer = "NO"
print(answer)

Measured memory_bytes: 3060
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
	int n;
	long long X = 0, x = 0, ans = 1000000000000000000LL;
	cin >> n;
	vector<long long> a(n);
	for (int i = 0; i<n; i++) {
		cin >> a[i];
		X += a[i];
	}
	for (int i = 0; i<n; i++) {
		x += a[i];
		if (i + 1<n)ans = min(ans, abs(X - 2 * x));
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <random>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T iabs(const T& x) { return max(x, -x); }
// #define abs gabs

int main() {
    i64 h, w;
    cin >> h >> w;
    i64 ans = 1e9;
    for (int k = 0; k < 2; ++k) {
        for (int i = 1; i < h; ++i) {
            i64 a = i * w;
            i64 g = h - i;
            {
                i64 b = g / 2 * w, c = (g - g / 2) * w;
                if (b != 0 && c != 0) {
                    ans = min(ans, max({a, b, c}) - min({a, b, c}));
                }
            }
            {
                i64 b = w / 2 * g, c = (w - w / 2) * g;
                if (b != 0 && c != 0) {
                    ans = min(ans, max({a, b, c}) - min({a, b, c}));
                }
            }
        }
        swap(h, w);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(I,X,Y) for(int (I)=(X);(I)<(Y);(I)++)
#define REP(I,X,Y) for(int (I)=(Y)-1;(I)>=(X);(I)--)
#define ALL(X) (X).begin(),(X).end()
#define INF 1000000007
#define LINF 1000000000000000007
typedef long long ll;
using namespace std;

int main(){
  string S;
  cin >> S;
  if(S.substr(0,4) == "YAKI")cout << "Yes" << endl;
  else cout << "No" << endl;
}


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)

la = 10**12+1
sm = -1
while sm+1<la:
    mi = (sm+la)//2
    y=0
    for i in range(N):
        y += max(0, A[i]-(mi//F[i]))
    if y<=K:
        la = mi
    else:
        sm = mi
print(la)

Measured memory_bytes: 113612
import java.util.Collections

import scala.io.StdIn

object Main {
  def main(args: Array[String]) = {
    val line = StdIn.readLine.split(" ").map(s => s.toInt)
    val N = line(0)
    val K = line(1)
    val x = StdIn.readLine.split(" ").map(s => s.toInt)

    var left = 0
    var right = left
    var ans = Int.MaxValue
    while(left < N) {
      while(right < N && right - left < K) {
        right+=1
      }

      if (right - left == K) {
        val l = x(left)
        val r = x(right-1)

        val max = Math.max(l.abs, r.abs)
        val min = Math.min(l.abs, r.abs)

        if (l < 0 && 0 <= r) {
          ans = Math.min(ans, min * 2 + max)
        } else {
          ans = Math.min(ans, max)
        }
      }
      left+=1
    }

    println(ans)
  }
}


Measured memory_bytes: 39936
#include <iostream>
#include <sstream>
#include <vector>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iomanip>
#include <vector>
#include <cstdio>
#include <float.h>
#include <queue>
#include <set>
#include <map>
#include <fstream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <stack>
#include <functional>
 
using namespace std;
 
#define endl '\n'
#define MOD 1000000007
#define INF 1ll<<30
#define MAX 100010
#define eps 1e-11
#define bit_max 1ll<<32
#define _USE_MATH_DEFINES

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 //   freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int ans[101010]={0};
    for(int i=n-2;i>=0;i--)
    {
        if(a[i]>=a[i+1])
            ans[i] = 1+ans[i+1];
        else
            ans[i] = 0;
    }
    int mx = 0;
    for(int i=0;i<n;i++)
    {
        mx = max(mx,ans[i]);
    }
    cout<<mx;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
//const int MOD=998244353;
const int INF=1e9;
const long long LINF=1e18;
#define int long long
//template
template <typename T>
void fin(T a){
  cout<<a<<endl;
  exit(0);
}
//main
signed main(){
  int N,M;cin>>N>>M;
  priority_queue<int> pque;
  while(N--){
    int a;cin>>a;
    pque.push(a);
  }
  while(M--){
    pque.push(pque.top()/2);
    pque.pop();
  }
  int ans=0;
  while(pque.size()){
    ans+=pque.top();
    pque.pop();
  }
  fin(ans);
}


Measured memory_bytes: 1400
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
int h,w;
int dx[]={0,1,0,-1};
int dy[]={-1,0,1,0};
string mp[101],str="NESW";;
ll n;

void solve(int x,int y,int dir){
  ll dis[4][101][101]={},cost=0;
  memset(dis,-1,sizeof(dis));
  while(n!=0){
    if(dis[dir][y][x]!=-1&&n%(cost-dis[dir][y][x])!=0){
      n%=(cost-dis[dir][y][x]);
      memset(dis,-1,sizeof(dis));
    }

    dis[dir][y][x]=cost;
    
    x+=dx[dir];
    y+=dy[dir];
    if(x<0||y<0||x>=w||y>=h||mp[y][x]=='#'){
      x-=dx[dir];
      y-=dy[dir];
      dir=(dir+1)%4;
    }
    else n--,cost++;
  }
  cout << y+1 <<" "<<x+1<<" "<<str[dir]<<endl;
}


int main(){
  while(1){
    cin >>h>>w>>n;
    if(!h&&!w&&!n)break;
    for(int i=0;i<h;i++) cin >> mp[i];
    
    int dir;
    for(int i=0;i<h;i++)
      for(int j=0;j<mp[i].size();j++)
	if(mp[i][j]!='.'&&mp[i][j]!='#'){
	  if(mp[i][j]=='N')dir=0;
	  if(mp[i][j]=='E')dir=1;
	  if(mp[i][j]=='S')dir=2;
	  if(mp[i][j]=='W')dir=3;
	  solve(j,i,dir);
	}
  }
  return 0;
}

Measured memory_bytes: 1568
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string>
#include<string.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<deque>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<iostream>
#include <bitset>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(auto i=a;i<b;i++)
#define all(_x) _x.begin(), _x.end()
#define r_sort(_x) sort(_x.begin(), _x.end(), std::greater<int>())
#define vec_cnt(_a, _n) (upper_bound(all(_a), _n) - lower_bound(all(_a), _n))
#define vec_unique(_a) _a.erase(std::unique(all(_a)), _a.end());
ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a % b); }
//ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
#define INF 1 << 30
const int mod = 1000000007;
int main() {
	int n;
	cin >> n;
	vector<int> h(n);
	rep(i, 0, n)cin >> h[i];
	h[0]--;
	rep(i, 1, n) {
		if (h[i] > h[i - 1])h[i]--;
	}
	rep(i, 0, n - 1) {
		if (h[i] > h[i + 1]) {
			puts("No");
			return 0;
		}
	}
	puts("Yes");
	return 0;
}


Measured memory_bytes: 640
#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;

ll dp[50][3];

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

	ll A, B, C, K; cin >> A >> B >> C >> K;
	ll res = 0LL;
	if (K % 2 == 0){
		res = A - B;
	}else{
		res = B - A;
	} // end if

	if (abs(res) > (ll)1e18){
		cout << "Unfair" << endl;
	}else{
		cout << res << endl;
	} // end if

	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <functional>
double amount=0;
using namespace std;


/*void printvec(vector<int> v) {
	int a = v.size();
	for (int i = 0; i < a; i++) {
		printf("%d ", v[i]);
	}
	printf("\n");
}*/


int main(){
    int N,K,i;
	vector<int> sp = {0};
    scanf("%d%d",&N,&K);
    int HP[N]={0};
    for(i=0;i<N;i++){
      scanf("%d",&HP[i]); 
	  sp.push_back(HP[i]);
    }
	sort(sp.begin(), sp.end());
	for (i = 0; i <= N-K; i++)
		amount += sp[i];
	//printvec(sp);
    printf("%.0f\n",amount);
    return 0;
}

Measured memory_bytes: 2168
import sys
def input(): return sys.stdin.readline().strip()


def main():
    n, m = map(int, input().split())
    A = list(map(int, input().split()))

    num = 0
    s = sum(A)
    for a in A:
        if a >= s / (m * 4):
            num += 1
    if num >= m:
        print("Yes")
    else:
        print("No")


if __name__ == "__main__":
    main()

Measured memory_bytes: 38704
# coding: utf-8

n = int(input())
S = input()

Wcnt = [0]
for i in range(n):
    if S[i] == "W":
        Wcnt.append(Wcnt[i]+1)
    else:
        Wcnt.append(Wcnt[i])

#左からi番目の人をリーダーに任命した場合に向く方向を変える人数を
#c[i]に格納する。
C = []

for i in range(n):
    cl = Wcnt[i]-Wcnt[0]
    cr = n-i-1-(Wcnt[n]-Wcnt[i+1])
    C.append(cl + cr)
    
print(min(C))

Measured memory_bytes: 64984
#include <cstdio>
#include <string>
#include<iostream>
#include<cstring>
using namespace std;
int son[5000];
int bro[5000];
char da[5000];
int award[5000];
int tot=1;
char a[20];
void Incert(int b){
    int i=0;
    if(son[0]==0){
        son[0]=tot;
        da[tot++]=a[i];
    }
    int j=son[0];
    while(i<strlen(a)){
        if(da[j]!=a[i]){
            if(bro[j]==0){
                bro[j]=tot;
                da[tot++]=a[i];
            }
            j=bro[j];
        }
        else {i++;
            if(son[j]==0){
                son[j]=tot;
                da[tot++]=a[i];
            }
            j=son[j];
        }
    }
    award[j]+=b;
}
int main(){
    int N,M,res=0;
    for(int i=0;i<4000;i++){
        award[i]=0;
        son[i]=0;
        bro[i]=0;
        da[i]=0;
    }
    scanf("%d%*c",&N);
    for(int i=0;i<N;i++){
        scanf("%s%*c",a);
        Incert(1);
    }
    scanf("%d%*c",&M);
    for(int i=0;i<M;i++){
        scanf("%s%*c",a);
        Incert(-1);
    }
    for(int i=0;i<=tot;i++){
        res=max(res,award[i]);
    }
    printf("%d",res);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define  vi vector<long long int>
#define  set1 set<long long int>
#define  pb push_back
#define  map1 map<long long int,long long int>
#define  ll    long long int
#define  mp make_pair
#define  inf 1e17
#define  minf INT_MIN
#define  setbits(x) __builtin_popcountll(x)
#define  pres(x,y) fixed<<setprecision(y)<<x
#define  pair1 pair<long long int,long long int>
#define  mk(arr,n,type) type *arr=new type[n];
#define  mod 1000000007
#define  pi  3.1415926535897932384626433832
#define  ins insert
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
//find_by_order() --> returns an iterator to the k-th largest element (counting from zero)
//order_of_key()  --> the number of items in a set that are strictly smaller than our item.
#define  w(t) long long int t;t=1;while(t--)

void solve() {

	ll n, w;
	cin >> n >> w;
	ll wt[n], val[n];
	for (ll i = 0; i < n; i++) {
		cin >> wt[i] >> val[i];
	}

	ll dp[n + 1][w + 1];

	memset(dp, 0, sizeof(dp));

	for (ll i = 1; i <= n; i++) {
		for (ll j = 1; j <= w; j++) {
			if (wt[i - 1] <= j) {
				dp[i][j] = max(dp[i - 1][j], val[i - 1] + dp[i - 1][j - wt[i - 1]]);
			}
			else {
				dp[i][j] = (dp[i - 1][j]);
			}
		}
	}
	cout << dp[n][w] << "\n";

}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
#ifndef ONLINE_JUDGE
	freopen("inp.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	w(t) {
		solve();
	}
	return 0;
}

Measured memory_bytes: 82344
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N,K;
  cin>>N>>K;
  string S;
  cin>>S;
  if(S.at(K-1)=='A'){
    S.at(K-1) = 'A' + 32;
    cout<<S<<endl;
  }
  else if(S.at(K-1)=='B'){
    S.at(K-1) = 'B' +32;
    cout<<S<<endl;
  }
  else if(S.at(K-1)=='C'){
    S.at(K-1) = 'C' + 32;
    cout<<S<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <string.h>
#include <math.h>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <deque>
#include <queue>
#include <functional>
//#include <boost/multiprecision/cpp_int.hpp>

#define rep(i, n) for(int i = 0; i < n; ++i)
#define REP(i, m, n) for(int i = m; i < n; ++i)
#define rrep(i,n) for(int i = n; i >= 0; --i)
#define RREP(i, m, n) for(int i = n; i >= m; --i)
#define llrep(i, n) for(ll i = 0; i < n; ++i)
#define llREP(i, m, n) for(ll i = m; i < n; ++i)
#define llrrep(i,n) for(ll i = n; i >= 0; --i)
#define llRREP(i, m, n) for(ll i = n; i >= m; --i)

using ll = long long;
using ull = unsigned long long;
using pii = std::pair<int, int>;
using pll = std::pair<long long, long long>;
using pil = std::pair<int, long long>;
using pli = std::pair<long long, int>;
using plpii = std::pair<long long, std::pair<int, int>>;
using pdd = std::pair<double, double>;

const long long INF = 1000000000000000001;
const long long _MOD = 1000000007;
const long long MOD = 998244353;
const int ALPHABET = 27;
const double pi = 3.14159265358979;

using namespace std;
//namespace mp = boost::multiprecision;

ll f(ll n, ll x) {
	if (x <= 0) return 0;
	if (n == 0) return 1;

	if (((ll)1 << n + 1) - 3 >= x - 1) {
		return f(n - 1, x - 1);
	}
	else {
		return ((ll)1 << n) + f(n - 1, x - 2 - (((ll)1 << n + 1) - 3));
	}
}

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

	ll n, x;
	cin >> n >> x;
	cout << f(n, x) << "\n";

	return 0;
}


Measured memory_bytes: 3648
arr = []
i=0
loop do
  a, b = gets.chomp.split(' ').map(&:to_i)
  if a == 0 && b==0
    arr.each {|i| puts i[0].to_s+' '+i[1].to_s}
    break
  else
    if a < b
      arr.push([a, b])
    else
      arr.push([b, a])
    end
  end
  i+=1
end

Measured memory_bytes: 8724
#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<map>
#include<string>
using namespace std;

int main() {
	int N, C[200005];
	string S;
	cin >> N >> S;

	C[0] = 0;

	for (int i = 0; i < N; i++) {
		C[i + 1] = C[i];
		if (S.at(i) == '.') C[i + 1]++;
	}

	int ans = 2000000;
	for (int i = 0; i <= N; i++) {
		int cnt = i - C[i] + C[N] - C[i];
		ans = min(ans, cnt);
	}

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


Measured memory_bytes: 1412
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>

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

int main() {

	string s;
	cin >> s;

	int ans = 0;
	rep(i, s.size())
		if (s[i] == '1')
			ans++;
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef long long ll;

#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=(b-1);i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;

#define MOD 1000000007

int main() {
	ll n,y;
	cin>>n>>y;
	ll flag = 0;
	rep(i,0,2001){
		rep(j,0,2001){
			ll k = n-i-j;
			if(k<0)continue;
			if(10000*i+5000*j+1000*k==y){
				cout << i << " " << j << " " << k << endl;
				return 0;
			}
		}
	}
	cout << -1 << " " << -1 << " " << -1 << endl;
	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define FI first.first
#define SE first.second
#define TH second
#define fi first
#define se second
#define th second

using namespace std;

template<typename T>
string to_string(const vector<T>& vc, int w) {
	if(vc.empty()) return "";
	if(w + 1 == vc.size()) return to_string(vc[w]);
	return to_string(vc[w]) + "," + to_string(vc, w + 1);
}

template<typename T>
string to_string(const vector<T>& vc) {
	return "{" + to_string(vc, 0) + "}";
}

void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
 
#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

class DebugStream {}LOG;
template <typename T>DebugStream &operator<<(DebugStream &s, const T&) { return s; }
#ifdef DEBUG
#define LOG clog
#endif

typedef long long ll;
typedef pair<ll, ll> ii;
typedef long double ld;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int maxN = 1e5 + 9, maxV = 1e6 + 9, SQ = 335, lg = 20, bs = 29;
const ll MOD = 2725070293067;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	#endif

	int n;
	cin >> n;
	vector<string> arr(n);
	for(auto& el: arr) cin >> el;
	sort(arr.begin(), arr.end(), [](const string& a, const string& b) {
		return a.size() < b.size();
	});

	ll ans = 0;
	map<ll, map<char, ll>> mp;
	for(auto str: arr) {
		vector<ll> lkp(bs), hist(bs);
		ll hsh = 0;
		for(int i = int(str.size()) - 1; i >= 0; i--) {
			const auto& tbl = mp[hsh];
			for(auto el: tbl) lkp[el.fi - 'a'] += el.se;
			if(i == 0) mp[hsh][str[0]]++;
			hist[str[i] - 'a'] = lkp[str[i] - 'a'];
			hsh = (hsh * bs + str[i] - 'a' + 1) % MOD;
		}
		ans += accumulate(hist.begin(), hist.end(), 0LL);
	}
	cout << ans << '\n';
}



Measured memory_bytes: 98192
#include <stdio.h>
#include <utility>
using namespace std;
#define F first
#define S second
#define PB push_bacl
typedef pair<int,int>pi;
const int N=1e2+10;
long long int abs(long long int n){return n>0?n:-n;}
int main(){
    int n;
    pi a[N];
    long long int ans=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d%d",&a[i].F,&a[i].S);
    a[n]=a[0];
    for(int i=0;i<n;i++)ans+=a[i].F*a[i+1].S;
    for(int i=0;i<n;i++)ans-=a[i].S*a[i+1].F;
    ans=abs(ans);
    printf("%.1lf\n",(double)ans/2);
}


Measured memory_bytes: 2720
#include<iostream>
#include <string>
#include<vector>
typedef long long ll;

using namespace std;
int main()
{
	int n;
	cin >> n;

	string kotae = "No";

	for (int i = 0; i <= n / 4; i++) {
		for (int j = 0; j <= n / 7; j++) {
			if (4 * i + 7 * j == n) kotae = "Yes";
		}
	}

	cout << kotae << endl;
	return 0;
}

Measured memory_bytes: 256