akhauriyash/Code-Regression huggingface dataset:
N=int(input())
A=list(map(int,input().split()))
A.sort()
Amax=A[-1]
dp=[True]*(Amax+1)
ans=0
for i in range(N-1):
    p=A[i]
    if dp[p]:
        for j in range(1,Amax//p+1):
            dp[p*j]=False
        if p!=A[i+1]:
            ans+=1
if dp[Amax]:
    ans+=1
print(ans)

        




    









        

    









    

        




    















    



    





    






        






    
















        


























            
    


    


    
    














    


    














Measured memory_bytes: 32112
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
template <typename T>
inline void read(T &x) {
	x = 0;
	bool sign = false;
	char ch = getchar();
	while (ch < '0' || '9' < ch) {
		sign |= ch == '-';
		ch = getchar();
	}
	while ('0' <= ch && ch <='9') {
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	x = sign ? -x : x;
}
template <typename T>
inline void print(T x) {
	static char outp[128];
	int tot = 0;
	if (!x) {
		putchar('0');
		return;
	} else if (x < 0) {
		x = -x;
		putchar('-');
	}
	while (x) { outp[tot++] = x % 10, x /= 10; }
	while (tot) { putchar(outp[--tot] + 48); }
}
typedef long long lint;
typedef unsigned int uint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
typedef unsigned long long ulint;
#define endl '\n'
#define fst first
#define sed second
#define pb push_back
#define mp make_pair
#define rint register int
#define newline putchar('\n')
#define leave_space putchar(' ')
#define all(x) (x).begin(), (x).end()
#define reveal(x) cerr << #x << " = " << (x) << endl
#define rep(it, f, e) for (rint it = (f); it <= (e); ++it)
#define per(it, f, e) for (rint it = (f); it >= (e); --it)
const int MOD = 1e9 + 7;
int dp[108][256][108], ary[108], n, p;
inline int dfs(int i, int j, int k) {
	if (i == n + 1) {
		return (j == p && k == 0);
	}
	if (~dp[i][j][k]) return dp[i][j][k];
	int ret = dfs(i + 1, j, k);
	if (k) ret += dfs(i + 1, j ^ ary[i], k - 1);
	return dp[i][j][k] = ret % MOD;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n >> p;
	rep (i, 1, n) {
		cin >> ary[i];
	}
	int poww = 1;
	memset(dp, -1, sizeof(dp));
	int ans = dfs(1, 0, 0);
	rep (i, 1, n) {
		poww = poww * 1ll * i % MOD;
		ans = (ans + poww * 1ll * dfs(1, 0, i)) % MOD;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 11904
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define eb emplace_back
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 233;
vector<int> g[maxn];
int f[maxn],u[maxn],v[maxn],d[maxn];
ll p[100];
bool vis[100];
void dfs(int x,int fa){
	f[x] = fa;
	for(int y:g[x]){
		if(y==fa)continue;
		d[y] = d[x]+1;
		dfs(y,x); 
	}
}
ll lca(int x,int y){
	ll s = 0;
	if(d[x]<d[y])swap(x,y);
//	cout<<"!!!!!!!!"<<x<<" "<<y<<endl;
	while(d[x]>d[y]){
		vis[x] = 1;
		s ^= 1LL<<x;
		x = f[x];
	}
	if(x==y)return s;
	while(x!=y){
		vis[x] = 1;
		s ^= 1LL<<x;
		x = f[x];
		
		vis[y] = 1;
		s ^= 1LL<<y;
		y = f[y];
		
		
	}
	return s;
}
ll mask[maxn];
int main()
{
	int n;cin>>n;
	for(int i=1;i<n;i++){
		int x,y;scanf("%d%d",&x,&y);
		g[x].pb(y);
		g[y].pb(x);
	}
	d[1] = 1;
	dfs(1,0);
	int m;cin>>m;
	for(int i=0;i<m;i++){
		scanf("%d%d",&u[i],&v[i]);
		mask[i] = lca(u[i],v[i]);
//		cout<<"->"<<i<<" "<<mask[i]<<endl; 
	}
	p[0] = 1;
	for(int i=1;i<=50;i++)p[i] = p[i-1]*2;
	ll ans = 0;
	for(int i=0;i<(1<<m);i++){
		memset(vis,0,sizeof(vis));
		int op = 1;
		ll cur = 0;
		for(int j=0;j<m;j++)
			if(i&(1<<j)){
				op = -op;
				cur |= mask[j];
			}
		int cnt = 0;
		for(int j=2;j<=n;j++)
			if((cur&(1LL<<j))==0)cnt++;
		ans += op*p[cnt];
//		cout<<"!"<<i<<" "<<cnt<<" "<<cur<<endl;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 7552
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
template<class T> void chmin(T& x, T y){if(x > y) x = y;}
template<class T> void chmax(T& x, T y){if(x < y) x = y;}
int N;
int H[100010];

int main(){
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> H[i];
    }
    bool flag = true;
    for(int i = 1; i < N; i++){
        if(H[i] > H[i - 1]) H[i]--;
        if(H[i] < H[i - 1]) flag = false;
    }
    cout << (flag ? "Yes" : "No") << endl;
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;
static bool dp1[10];
static bool dp2[100];
static bool dp3[1000];

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	string s;
	cin >> n >> s;
	memset(dp1, 0, sizeof(dp1));
	memset(dp2, 0, sizeof(dp2));
	memset(dp3, 0, sizeof(dp3));
	for(const int c : s){
		const int d = c - '0';
		for(int i = 0; i < 100; ++i){
			if(dp2[i]){ dp3[i * 10 + d] = true; }
		}
		for(int i = 0; i < 10; ++i){
			if(dp1[i]){ dp2[i * 10 + d] = true; }
		}
		dp1[d] = true;
	}
	int answer = 0;
	for(int i = 0; i < 1000; ++i){
		if(dp3[i]){ ++answer; }
	}
	cout << answer << endl;
	return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
//----***やべーやつら***----
using namespace std;
#define int long long

//----***型定義***----
using ll = long long;
using P = pair<int,int>;

//----***Like a Pythonista***----
#define REP(ii,jj,nn) for (ll ii=jj;ii<(nn);ii++)
#define RREP(ii,nn,jj) for (ll ii = nn; jj<ii;ii--)
#define each(i,...) for (auto&& i:__VA_ARGS__)
#define ALL(vec) (vec).begin(),(vec).end()
#define sum(...) accumulate(ALL(__VA_ARGS__),0LL)
#define dsum(...) accumulate(ALL(__VA_ARGS__),0.0)
#define vec(type,name,...) vector<type> name(__VA_ARGS__)
template<class T> inline auto max(const T& a){ return *max_element(ALL(a)); }
template<class T> inline auto min(const T& a){ return *min_element(ALL(a)); }
inline ll gcd(ll a,ll b){if(b == 0) return a;return  gcd(b,a%b);}
inline ll lcm(ll a,ll b){ll g = gcd(a,b);return a / g * b;}

//----***定数***----
#define MOD 1000000007
#define INF 100000000000000000
#define EPS 1e-9
#define PI  acos(-1)
const vector<vector<int>> DXY={{-1,0},{1,0},{0,-1},{0,1}};

//----***パーツ***----
#define fi first
#define se second
#define pb push_back
#define re return
#define br break

//----***入出力***---
void print() { std::cout << "\n"; }
template <class T>void print(const T &x) {std::cout << x<<"\n";}
template <class T, class... Args>void print(const T &x, const Args &... args) {std::cout << x << " ";print(args...);}
#define debug(var)  do{std::cerr << #var << " ↓ "<<"\n";view(var);}while(0);
#define dbg cerr<<"🥺🥺🥺🥺🥺🥺"<<endl;
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }

//----***初期時読み込み***----
struct initial{initial(){cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(15);};}initial_;

int N,M;
string S;

int GetDigit(int num){
    int digit=-1;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
}

signed main(){
  cin>>N;
  vector<int> arr(N);
  REP(i,0,N)cin>>arr[i];
  sort(ALL(arr));
  // debug(arr);
  int a=arr[0];
  REP(i,1,N){
    // print(GetDigit(a),GetDigit(arr[i]));
    if(GetDigit(a)+GetDigit(arr[i])>18||(a>1000000000000000000/arr[i])){
      print(-1);
      re 0;
    }
    a*=arr[i];
  }
  print(a);

}


Measured memory_bytes: 3996
#include <bits/stdc++.h>
using longlong=long long;

int main(){
    std::cin.tie(nullptr);std::cin.sync_with_stdio(false);
    int a,b,c,d;std::cin>>a>>b>>c>>d;
    std::cout<<std::min(a,b)+std::min(c,d)<<std::endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>

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

using namespace std;

int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	printf("%d\n",max(max(a+b,a-b),a*b));

	return 0;
}


Measured memory_bytes: 128
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007

int N, K;
map<int, int> C;

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N >> K;
  rep(i, N) {
    int a;
    cin >> a;
    C[a]++;
  }
  if (C.size() <= K) {
    cout << 0 << "\n";
    return 0;
  }
  int num = C.size()-K;
  vector<int> xs;
  for (auto p : C) xs.pb(p._2);
  sort(all(xs));
  int sum = 0;
  rep(i, num) sum += xs[i];
  cout << sum << "\n";
  return 0;
}


Measured memory_bytes: 10744
#include <iostream>

using namespace std;



bool isPrime(int n) {
	if (n<2) return false;
	for (int i=2; i * i <= n; i++) {
		if (n%i == 0) return false;
	}
	return true;
}

int main() {
	
	while (1) {
		int a, d, n; cin >> a >> d >> n; if (a==0 && d==0 && n==0) break;
		
		int i = 0;
		int number = a;
		while (1) {
			if (isPrime(number)) i++;
			if (i == n) break;
			number += d;
		}
		cout << number << endl;		
	}
	
	return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

int main() {
    double n, m, d;
    cin >> n >> m >> d;
    double ans = 2 * (n - d) / n / n * (m - 1);
    if (d == 0) ans = (m - 1) / n;
    printf("%.15f\n", ans);
    return 0;
}

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

int main(){
    int n,q;
    cin >> n >> q;
    string s;
    cin >> s;
    vector<int> l(q),r(q);
    for(int i=0;i<q;i++){
        cin >> l[i] >> r[i];
    }
    vector<int> sum(n);
    for(int i=0;i<n-1;i++){
        sum[i+1]=sum[i];
        if(s[i]=='A' && s[i+1]=='C')
            sum[i+1]++;
    }
    for(int i=0;i<q;i++){
        int ans=sum[r[i]-1] - sum[l[i]-1];
        cout << ans << endl;
    }
}

Measured memory_bytes: 2176
#include <vector>
#include <iostream>
#include <cmath>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <fstream>
#include <unistd.h>
#include <string>
#include <numeric>
#include <queue>
#include <deque>
#include <sstream>
#include <iomanip>
#include <set>
#include <stack>
#include <cassert>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vvb> vvvb;
typedef vector<vvvb> vvvvb;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<vvd> vvvd;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef vector<P> vp;
typedef vector<PL> vpl;
typedef vector<vector<P>> vvp;
typedef vector<vector<PL>> vvpl;
const int INF = 1001001001;
const ll LINF = 1e16;
const double pi = 3.1415926535897932;
const string endstr = "\n";
#define FOR(i, a, b) for(ll i = (a); i < b; i++)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define FORMAP(it, m) for(auto it = m.begin(); it != m.end(); it++)
#define ff first
#define ss second
#define pb push_back

template <typename T>
T gcd(T a, T b) {
    return (a == 0) ? b : gcd(b%a, a);
}
template <typename T>
T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

bool p_comp_fs(const PL p1, const PL p2){ return p1.first < p2.first;};
bool p_comp_fg(const PL p1, const PL p2){ return p1.first > p2.first;};
bool p_comp_ss(const PL p1, const PL p2){ return p1.second < p2.second;};
bool p_comp_sg(const PL p1, const PL p2){ return p1.second > p2.second;};
template <typename T>
vector<T> uniquen(vector<T> vec){
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    return vec;
}

//using edge = struct{ll from, to;};

int main(){
    ll N, T; cin >> N >> T;
    vl A(N); REP(i, N) cin >> A[i];
    ll mxgain = 0; ll mna = LINF;
    vl gains(N);
    REP(i, N){
        if(i==0){
            gains[0] = 0;
            mna = A[0]; continue;
        }
        gains[i] = max(A[i]-mna, 0ll);
        mxgain = max(mxgain, A[i]-mna);
        mna = min(mna, A[i]);
    }
    
    ll ans = 0; ll l = 0;
    while(l < N){
        ll r = l;
        ll mncnt = 0, mxcnt = 0;
        mna = A[l];
        while(r < N && mna <= A[r]){
            if(A[r] - mna == gains[r] && gains[r] == mxgain) mxcnt++;
            if(A[r] == mna) mncnt++;
            r++;
        }
        ans += min(mncnt, mxcnt);
        mna = min(mna, A[r]);
        l = r;
    }
    cout << ans << endl;
    return 0;
}


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

typedef long long ll;
typedef long double ld;

#define pb push_back
#define sort(s) sort(s.begin(),s.end())
#define reverse(s) reverse(s.begin(),s.end())
#define rep(i,n) for(ll (i)=0;(i)<(n);(i)++)

const ll mod = 1e9+7;

//最大公約数
ll gcd(ll a, ll b) {
    return b ? gcd(b, a%b) : a;
}

//最小公倍数
ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

//素数判定
bool isPrime(ll x){
    ll i;
    if(x < 2)return 0;
    else if(x == 2) return 1;
    if(x%2 == 0) return 0;
    for(i = 3; i*i <= x; i += 2) if(x%i == 0) return 0;
    return 1;
}

//桁和
int digsum(ll n) {
    int res = 0;
    while(n > 0) {
        res += n%10;
        n /= 10;
    }
    return res;
}

//桁数
int dignum(ll n) {
    int res = 0;
    while(n > 0) {
        res++;
        n /= 10;
    }
    return res;
}

//文字列中の特定の文字カウント
ll stringcount(string s,char c){
    return count(s.cbegin(),s.cend(),c);
}

//階乗
ll ka(ll i){
    ll res=1;
    while(i>0){
        res=res*i;
        i--;
    }
    return res;
}
 
//ncr
ll ncr(ll x,ll y){
    ll a = x;
    ll b = 1;
    if(y>(x/2)){
        y=x-y;
    }
    for(ll i=1;i<y;i++){
        a*=x-i;
        b*=i+1;
    }
    return a/b;
}

//フィボナッチ数列 -92
ll f(ll x){
    ll dp[x+1];
    dp[1]=1;
    dp[2]=1;
    for(ll i=3;i<=x;i++){
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[x];
}



int main(){
    int n;
    string s;
    cin >> n;
    cin >> s;

    map<char,ll> mp;

    for(int i=0;i<n;i++){
        mp[s[i]]++;
    }

    ll ans = mp['R']*mp['G']*mp['B'];

    for(int i=0;i<n;i++){
        for(int j=i+1;2*j-i<n;j++){
            if(s[i] != s[j] && s[i]!=s[2*j-i] && s[j] != s[2*j-i]){
                ans--;
            }
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 3628
#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<deque>
#include<ctime>
#include<vector>
#include<bitset>
#include<string>
#include<cstdio>
#include<numeric>
#include<utility>
#include<sstream>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<unordered_map>
#define _USE_MATH_DEFINES
#define inf 999999999999999999
#define rep(i,n,m) for(lli i=(lli)(n);i<(lli)(m);++i)
#define reep(i,n,m) for(int i=(int)(n);i<=(int)(m);++i)
#define per(i,m,n) for(lli i=(int)(m)-1;i>=(int)(n);--i)
#define st(n) sort(n.begin(), n.end())
#define rev(n) reverse(n.begin(),n.end())
#define ou(S) cout << S << endl
#define pb(n) push_back(n)
#define ue(N) N.erase(unique(N.begin(),N.end()),N.end());
#define nou(S) cout << S
#define hou(S) cout << setprecision(30) << S << endl
#define vec(K,L,N,S) vector<L> K(N,S)
#define dv(K,L,N,M,S) vector<vector<L>> K(N,vector<L>(M,S))
#define tv(K,L,N,M,R,S) vector<vector<vector<L>>> K(N,vector<vector<L>>(M,vector<L>(R,S)))
#define pint pair<lli,lli>
#define paf(L,R) pair<L,R>
#define maxx 5100000
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define endl "\n"
typedef long long int lli;
typedef unsigned long long int uli;
const uli mod = 1e9+7;
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  
  int n,nam=0,han=0;
  cin>>n;
  vector<lli> a(n);
  rep(i,0,n)cin>>a.at(i);
  rep(i,0,n){
    if(a.at(i)%2==0){
      ++han;
      if(a.at(i)%3==0||a.at(i)%5==0)
        ++nam;
    }
  }
  if(han==nam)
    ou("APPROVED");
  else ou("DENIED");
}

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

using namespace std;

#define mz 1000000007

int num[100005];

int main()
{
    int n,ans=0,m;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&m);
        if(m>100000)
            ans++;
        else
            num[m]++;
    }
    for(int i=1;i<=100000;i++)
    {
        if(num[i]<i)
            ans+=num[i];
        else
            ans+=num[i]-i;
    }
    cout<<ans<<endl;
    return 0;
}


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

#define IL __inline__ __attribute__((always_inline))

#define For(i, a, b) for (int i = a, i##end = b; i <= i##end; ++ i)
#define FOR(i, a, b) for (int i = a, i##end = b; i < i##end; ++ i)
#define Rep(i, a, b) for (int i = a, i##end = b; i >= i##end; -- i)
#define REP(i, a, b) for (int i = (a) - 1, i##end = b; i >= i##end; -- i)

typedef long long LL;

template <class T>
IL bool chkmax(T &a, const T &b) {
  return a < b ? ((a = b), 1) : 0;
}

template <class T>
IL bool chkmin(T &a, const T &b) {
  return a > b ? ((a = b), 1) : 0;
}

template <class T>
IL T mymax(const T &a, const T &b) {
  return a > b ? a : b;
}

template <class T>
IL T mymin(const T &a, const T &b) {
  return a < b ? a : b;
}

template <class T>
IL T myabs(const T &a) {
  return a > 0 ? a : -a;
}

const int INF = 0X3F3F3F3F;
const double EPS = 1E-10, PI = acos(-1.0);

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define OK DEBUG("Passing [%s] in LINE %d...\n", __FUNCTION__, __LINE__)
/*------------------------------header------------------------------*/

const int MAXN = 100 + 5;

char str[MAXN][MAXN];
int cnt[MAXN][MAXN], f[MAXN][MAXN][MAXN][MAXN];

IL int getSum(int x1, int y1, int x2, int y2) {
  return cnt[x2][y2] - cnt[x1 - 1][y2] - cnt[x2][y1 - 1] + cnt[x1 - 1][y1 - 1];
}

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  int x, y;
  For(i, 1, n) {
    scanf("%s", str[i] + 1);
    For(j, 1, m) {
      if (str[i][j] == 'E') {
        x = i, y = j;
      } else if (str[i][j] == 'o') {
        cnt[i][j] = 1;
      }
    }
  }
  For(i, 1, n) {
    For(j, 1, m) {
      cnt[i][j] += cnt[i - 1][j] + cnt[i][j - 1] - cnt[i - 1][j - 1];
    }
  }
  FOR(i, 0, x) {
    For(j, 0, n - x) {
      FOR(k, 0, y) {
        For(l, 0, m - y) {
          int cur = f[i][j][k][l];
          if (i < x - 1) {
            if (x - i - 1 > j) {
              chkmax(f[i + 1][j][k][l], cur + getSum(x - i - 1, mymax(l + 1, y - k), x - i - 1, mymin(y + l, m - k)));
            } else {
              chkmax(f[i + 1][j][k][l], cur);
            }
          }
          if (j < n - x) {
            if (x + j + 1 <= n - i) {
              chkmax(f[i][j + 1][k][l], cur + getSum(x + j + 1, mymax(l + 1, y - k), x + j + 1, mymin(y + l, m - k)));
            } else {
              chkmax(f[i][j + 1][k][l], cur);
            }
          }
          if (k < y - 1) {
            if (y - k - 1 > l) {
              chkmax(f[i][j][k + 1][l], cur + getSum(mymax(j + 1, x - i), y - k - 1, mymin(x + j, n - i), y - k - 1));
            } else {
              chkmax(f[i][j][k + 1][l], cur);
            }
          }
          if (l < m - y) {
            if (y + l + 1 <= m - k) {
              chkmax(f[i][j][k][l + 1], cur + getSum(mymax(j + 1, x - i), y + l + 1, mymin(x + j, n - i), y + l + 1));
            } else {
              chkmax(f[i][j][k][l + 1], cur);
            }
          }
        }
      }
    }
  }
  printf("%d\n", f[x - 1][n - x][y - 1][m - y]);
  return 0;
}


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

int main(){
	char X, Y, endptr;
	cin >> X >> Y;
	
	if(X>Y)		cout << '>' << endl;
	else if(X==Y)	cout << '=' << endl;
	else		cout << '<' << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<deque>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#include<iomanip>
#include<cassert>
#include<regex>
#include<bitset>
#include<complex>
#include<chrono>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;

ll gcd(ll n, ll m) {
	ll tmp;
	while (m!=0) {
		tmp = n % m;
		n = m;
		m = tmp;
	}
	return n;
}

ll lcm(ll n, ll m) {
	return abs(n * m) / gcd(n, m);//gl=xy
}
 
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
 
using namespace std;

//ここから
//桁DP
ll digit_dp(string s){
  int n=s.size();
  ll dp[n+1][2];
  rep(i,n+1){
    rep(j,2)dp[i][j]=INF;//jは繰り下がりの有無
  }
  reverse(all(s));
  dp[0][0]=0;
  //前の桁に戻りたくないので下から見ていく
  rep(i,n) {
		ll D = s[i] - '0';
    rep(j,2){
      D+=j;//繰り下がりで1引く=Nが+1
      chmin(dp[i+1][1],dp[i][j]+10-D);
      chmin(dp[i+1][0],dp[i][j]+D);
    }
	}
  ll ans=min(dp[n][1]+1,dp[n][0]);//最後に繰り下がりが発生するパターンは自分で繰り下がりを作るので+1
  return ans;
}


void solve(){
  string s;
  cin>>s;
  ll x=digit_dp(s);
  cout<<x<<"\n";
}

int main(){
	ios::sync_with_stdio(false);
  cin.tie(0);
	cout<<fixed<<setprecision(15);
  solve();
	return 0;
}


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

int s, k;
int c = 0;

int main() {
    std::cin >> k >> s;
    for (int i = 0; i <= k; i++) {
        for (int p = 0; p <= k; p++) {
            if (s - i - p >= 0 && s-i-p <= k) {
                c++;
            }
        }
    }
    std::cout << c << std::endl;
}


Measured memory_bytes: 256
A = int(input())
B = int(input())
C = int(input())
X = int(input())
ans = 0
for i in range(0,A+1):
    for j in range(0,B+1):
        for _ in range(0,C+1):
            if 500*i+100*j+_*50 == X:
                ans += 1
print(ans)

Measured memory_bytes: 3060
#include<algorithm>
#include<climits>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<list>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<utility>
#include<vector>

using namespace std;

#define lint long long
#define REP(i, x, n) for(int i = x ; i < n ; i++)
#define rep(i, n) REP(i, 0, n)
#define repr(i, n) for(int i = n - 1 ; i >= 0 ; i--)
#define SORT(c) sort((c).begin(), (c).end())
#define SORT_INV(c) sort((c).begin(), (c).end(), greater<int>())
#define IINF (int)(1e9+10)
#define LLINF (lint)(1e18+10)

int main(){
    int n;
    cin >> n;
    set<string> st;
    string s, prev;
    cin >> s;
    prev = s;
    st.insert(s);
    bool flag = true;
    rep(i, n-1){
        cin >> s;
        if(st.count(s) || s[0] != prev[prev.size()-1]){
            flag = false;
        }
        prev = s;
        st.insert(s);
    }
    if(flag){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    vector<ll> A(N),B(N),C(N);
    for (int i=0;i<N;++i) cin >> A[i],B[i]=C[i]=A[i];
    vector<ll> left(N+1,0),right(N+1,0);
    left[1]=1;
    stack<pair<int,ll>> margin;
    for (int i=1;i<N;++i){
        ll cnt=0,m=0,b=B[i];
        if (B[i-1]<B[i]) while (B[i-1]<B[i]) B[i-1]<<=2LL,cnt+=2;
        else while ((b<<2LL)<=B[i-1]) b<<=2LL,m+=2;
        left[i+1]=left[i]+1;
        while (cnt&&!margin.empty()){
            auto p=margin.top(); margin.pop();
            ll now=min(cnt,p.second);
            left[i+1]+=now*(i-p.first);
            cnt-=now; p.second-=now;
            if (0<p.second) margin.push(p);
        }
        left[i+1]+=cnt*i;
        if (m) margin.emplace(i,m);
    }
    margin=decltype(margin)();
    for (int i=N-2;i>=0;--i){
        ll cnt=0,m=0,c=C[i];
        if (C[i+1]<C[i]) while (C[i+1]<C[i]) C[i+1]<<=2LL,cnt+=2;
        else while ((c<<2LL)<=C[i+1]) c<<=2LL,m+=2;
        right[i]=right[i+1];
        while (cnt&&!margin.empty()){
            auto p=margin.top(); margin.pop();
            ll now=min(cnt,p.second);
            right[i]+=now*(p.first-i);
            cnt-=now; p.second-=now;
            if (0<p.second) margin.push(p);
        }
        right[i]+=cnt*(N-1-i);
        if (m) margin.emplace(i,m);
    }
    ll ans=(ll)1e18;
    for (int i=0;i<N+1;++i) ans=min(ans,left[i]+right[i]);
    cout << ans << '\n';
}

Measured memory_bytes: 8064
while True:
    a, op, b = input().split()

    if op == '?':
        break

    if op == '+':
        print(int(a) + int(b))
    elif op == '-':
        print(int(a) - int(b))
    elif op == '/':
        print(int(a) // int(b))
    else:
        print(int(a) * int(b))



Measured memory_bytes: 5592
#include <stdio.h>
#include <string.h>

int main(void)
{
	int n,i;
	scanf("%d",&n);
	int s[n];
	for(i=0;i<=n-1;i++)
		{scanf("%d",&s[i]);}
	
	int min=s[0],max=s[0];
	for(i=0;i<=n-1;i++)
		{
		if(s[i]>max){max=s[i];}
		else if(s[i]<min){min=s[i];}
		}
	int dis=max-min;
	printf("%d",dis);
	return 0;
}


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

int main()
{
    int a[3];
    REP(i, 0, 3) cin >> a[i];
    sort(a, a + 3);
    if(a[0] + a[1] == a[2]) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
int m,n,X,Y,ix,iy,xmax = -101,ymin = 101,i;
scanf("%d %d %d %d",&n,&m,&X,&Y);
for(i = 0;i < n;i++){
scanf("%d",&ix);
if(xmax < ix){xmax = ix;}
}for(i = 0;i < m;i++){
scanf("%d",&iy);
if(ymin > iy){ymin = iy;}
}
if(xmax < ymin &&  xmax < Y && X < ymin){printf("No War\n");}
else{printf("War\n");}
return 0;
}


Measured memory_bytes: 128
def addEdge(adj, u, v):
    adj[u].append(v)
def dfs(node,dp,vis,adj):
    vis[node] = True 
    for i in range(len(adj[node])):
        if not vis[adj[node][i]]: 
            dfs(adj[node][i], dp,vis,adj)
        dp[node] = max(dp[node], 1 + dp[adj[node][i]])
import sys
sys.setrecursionlimit(10**9)
n, m = map(int, input().split())
adj = [[] for i in range(n + 1)] 
for i in range(m):
    u,v=map(int, input().split())
    addEdge(adj,u,v)
dp=[0]*(n+1)
vis=[False]*(n+1)
for i in range(1,n+1):
    if not vis[i]:
        dfs(i,dp,vis,adj)
ans=0
for i in range(1, n + 1):   
    ans = max(ans, dp[i])  
print(ans)


Measured memory_bytes: 132000
object Main extends App {
  val n =  scala.io.StdIn.readInt()
  val a = scala.io.StdIn.readLine()
  val aArray = a.split(" ").map(_.toInt).toVector
  val resultVec = aArray.zipWithIndex.map{ case(a, i) => (i + 1, a) }.sortBy(_._2).map(_._1)
  println(resultVec.mkString(" "))
}

Measured memory_bytes: 70128
#include <bits/stdc++.h>
using namespace std;
using lli = int_fast64_t;
using ulli = uint_fast64_t;
#define debug(x) cerr << #x << " : " << x << endl
#define debugv(x) cerr << #x << " : {";for(auto value_of_x:x){ cerr << value_of_x << ", ";}cerr << endl
#define debugvp(x) cerr << #x << " : {";for(auto value_of_x:x){ cerr << value_of_x.first << " : " << value_of_x.second << ", ";}cerr << endl
template<typename T>
T ncr(T left, T right) {
	right = min(left - right, right);
	T ans = 1;
	for (T i = 1; i <= right; i++) {
		ans = ans * (left - right + i) / i;
	}
	return ans;
}

const lli MOD = 1000000007;
const lli LIMIT = 1'0'000'000'000'000'000 * 5;
const int tenfive = 100000;

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

	string s;
	cin >> s;
	vector<int> v(N, 0);
	for (int i = 0; i < N; i++) {
		
		if (i > 0) {
			v[i] = v[i - 1];
			if (s.substr(i - 1, 2) == "AC") {
				v[i] += 1;
			}
		}
	}
	for (int i = 0; i < Q; i++) {
		int l, r;
		cin >> l >> r;
		cout << v[r - 1] - v[l - 1] << endl;
	}
	return 0;
}


Measured memory_bytes: 1408
import sys
from collections import deque
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    con = [[] for i in range(N)]
    ans = [0] * N

    for _ in range(N - 1):
        p, c = map(int, input().split())
        con[p-1].append(c-1)
        con[c-1].append(p-1)

    for _ in range(Q):
        p, v = map(int, input().split())
        ans[p-1] += v

    stacks = deque()
    stacks.append((0, -1))

    while stacks:
        stack = stacks.pop()
        node, parent = stack[0], stack[1]

        children = con[node]
        for child in children:
            if child == parent:
                continue
            ans[child] += ans[node]
            stacks.append((child, node))

    print(*ans)


if __name__ == '__main__':
    main()


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

#define ll long long
#define ull unsigned long long
#define mii make_pair<int, int>
#define mll make_pair<ll, ll>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define all(v) (v).begin(), (v).end()

//ofstream out("debug.txt");

const int MxN = 1e5, md = 1e9 + 7;

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

    int h, w, m;
    cin >> h >> w >> m;
    map<pii, int> p;
    map<int, int> r, c;
    for (int i = 0; i < m; ++i)
    {
        int a, b;
        cin >> a >> b;
        p[pii{a, b}]++;
        r[a]++;
        c[b]++;
    }
    int ma = 0, mb = 0;
    vi rs, cs;
    for (auto a : r)
        ma = max(ma, a.second);
    for (auto b : c)
        mb = max(mb, b.second);
    for (auto a : r)
        if (a.second == ma)
            rs.push_back(a.first);
    for (auto a : c)
        if (a.second == mb)
            cs.push_back(a.first);
    bool cr = 0;
    for (auto a : rs)
        for (auto b : cs)
            if (!p[pii{a, b}])
            {
                cout << ma + mb << '\n';
                return 0;
            }
    cout << ma + mb - 1 << '\n';
}

Measured memory_bytes: 54188
#include <bits/stdc++.h>
using namespace std;
//typedef
typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;
//define
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)

int main(){
  int a;
  rep(i,5){
      cin >> a;
    if(a == 0) cout << i+1 <<endl;
  }

    return 0;
}

Measured memory_bytes: 3636
#import <stdio.h>

int p(int x, int n) {
    int result = 1;
    while (n > 0) {
        if ((n % 2) == 0) {
            x *= x;
            n >>= 1;
        } else {
            result *= x;
            n--;
        }
    }
    return result;
}

int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    printf("%d",100*p(2,m)*(n+18*m));
    return 0;
}


Measured memory_bytes: 3648
#include <stdio.h>
#include <string.h>

int main(void)
{
  int wlen, linelen, i, count;
  char w[11];
  char line[1001];
  char *word;
  scanf(" %s", w);
  wlen = strlen(w);
  count = 0;
  while (1)
    {
      scanf(" %s", line);
      linelen = strlen(line);
      if (!strcmp("END_OF_TEXT", line))
	break;
      word = strtok(line, " ");
      while (word != NULL)
      	{
      	  if (!strcasecmp(w, &line[i]))
	    count++;
	  word = strtok(NULL, " ");
      	}
    }
  printf("%d\n", count);
  return 0;
}



Measured memory_bytes: 2076
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int main(void){
    int n, m;
    int k[30];
    int a[30][30];
    int d[31] = {0};
    
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> k[i];
        for(int j = 0; j < k[i]; j++){
            cin >> a[i][j];
            // cout << a[i][j] << endl;
            d[a[i][j]]++;
        }
    }

    int count = 0;

    for(int i = 0; i < 31; i++){
        if(d[i] == n){
            count++;
        }
    }

    cout << count << endl;

    return 0;
}

Measured memory_bytes: 256
// Copyright 2017 wu_qing
#include <cstdio>
const int N = 1e5 + 10;
int n, m, b[N], x, y, cnt;
bool h[N];
int main() {
    scanf("%d%d", &n, &m);
    h[1] = true;
    for (int i = 1; i <= n; i++)
        b[i] = 1;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &x, &y);
        if (h[x]) {
            h[y] = true;
            if (b[x] == 1)
                h[x] = false;
        }
        b[x]--;
        b[y]++;
    }
    for (int i = 1; i <= n; i++)
        if (h[i])
            cnt++;
    printf("%d\n", cnt);
    return 0;
}


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

int main()
{
    int N, K;
    cin >> N >> K;
    int n = N;
    vector<int> v(n), w(n);
    for (int i = 0; i < N; i++)
        cin >> v[i], --v[i];
    for (int i = 0; i < N; i++)
        cin >> w[i];

    ll ans = -1e18;
    for (int i = 0; i < n; i++)
    {
        vector<int> temp;
        int p = v[i];
        ll sum = 0, max_sum = w[p];
        ll sum_cycle = 0;
        while (p != i)
        {
            temp.push_back(w[p]);
            sum_cycle += w[p];
            max_sum = max(max_sum, sum_cycle);
            p = v[p];
        }
        temp.push_back(w[i]);
        sum_cycle += w[i];
        max_sum = max(max_sum, sum_cycle);
        int len = temp.size();
        if (sum_cycle <= 0)
            sum = max_sum;
        else{
            int number_cycle = K/len;
            int rem = K-number_cycle*len;
            ll temp_sum = 0;
            ll maxx = 0;
            for(int t = 0; t<rem ; t++){
                temp_sum += temp[t];
                maxx = max(temp_sum, maxx);
            }
            sum+=maxx + sum_cycle*number_cycle;
            ll next_sum = 0;
            if(number_cycle>1){
                next_sum = (number_cycle-1)*sum_cycle;
                next_sum+=max_sum;
            }
            sum = max(sum, next_sum);
        }
        ans = max(sum, ans);
    }
    cout<<ans;
}

Measured memory_bytes: 3700
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]

r = II()
import math
print(math.pi*r*2)

Measured memory_bytes: 9196
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define ll long long
using namespace std;
int main() 
{
	int n;
	scanf("%d",&n);
	ll a[100];
	a[0]=2;
	a[1]=1;
	for(int i=2;i<=n;i++)
	a[i]=a[i-1]+a[i-2];
	printf("%lld\n",a[n]);
	return 0;
}

Measured memory_bytes: 504
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<n;i++)
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
typedef long long ll;
const int mod= 1e+9+7;

int main() {
    ll N,M; cin>>N>>M;
    if(N>=2 && M>=2)cout<<(N-2)*(M-2)<<endl;
    else if(N==1&&M==1)cout<<1<<endl;
    else{
        ll a =max(N,M);
        cout<<a-2<<endl;
    }
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    // TODO 自動生成されたメソッド・スタブ
    Scanner scanner = new Scanner(System.in);
    long remainOfTakahashisCookie = scanner.nextLong();
    long remainOfAokisCookie = scanner.nextLong();
    long iterator = scanner.nextLong();
    if (iterator >= remainOfTakahashisCookie) {
      iterator -= remainOfTakahashisCookie;

      remainOfTakahashisCookie = 0;
      remainOfAokisCookie -= iterator;
    } else {
      remainOfTakahashisCookie -= iterator;
    }
    if (remainOfTakahashisCookie < 0) {
      remainOfTakahashisCookie = 0;
    }
    if (remainOfAokisCookie < 0) {
      remainOfAokisCookie = 0;
    }
    System.out.println(remainOfTakahashisCookie + " " + remainOfAokisCookie);
  }

}


Measured memory_bytes: 22612
#include<stdio.h>
#include<math.h>
long long yaku(long long c, long long d){
if(c<=d){
  long long w=c;
  c=d;
  d=w;
}
if(d==0)return c;
else return yaku(d,c%d);
}

long long lcm(long long c,long long d){
  return c/yaku(c,d)*d;
}

long long f(long long x,long long y,long long z){
long long ans=x;
  ans-=x/y;
  ans-=x/z;
  ans+=x/lcm(y,z);
  return ans;
}

int main(void){
   long long a,b,c,d;
  scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
  long long ans=f(b,c,d)-f(a-1,c,d);
  printf("%lld",ans);
  return 0;
}

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

int N;

int main(){
	while(cin >> N){
		set<int> s;
		for(int i=0;i<N;i++){
			int a;
			cin >> a;
			decltype(s)::iterator it = s.find(a);
			if(it !=s.end()) s.erase(a);
			else s.insert(a);
		}
		cout << s.size() << endl;
	}
}

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

#include<cstdio>
#define r(i,n) for(int i=0;i<n;i++)


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

  if(b%a==0)cout<<a+b<<endl;
  else cout<<b-a<<endl;



return 0;}


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

int main()
{
    int n;
    ll k;
    cin >> n >> k;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    
    vector<int> s;
    vector<int> ord(n + 1, -1);
    int c = 1;
    int l = 0;
    {
        int v = 1;
        while (ord[v] == -1) {
            ord[v] = s.size();
            s.push_back(v);
            v = a[v - 1];
        }
        c = s.size() - ord[v];
        l = ord[v];
    }

    if(k < l) cout << s[k] << endl;
    else {
        k -= l;
        k %= c;
        cout << s[l + k] << endl;
    }
    return 0;
}

Measured memory_bytes: 5888
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define ll long long
#define P pair<int,int>
#define rep(i,n) for(int i = 0; i < int(n); i++)
#define vi vector<int>
using namespace std;
const int INF = 1001001001;
const int MOD = 1e9+7;
template<class T> inline bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }

struct mint{ // auto MOD int
  ll x;
  mint(ll x=0) : x((x%MOD+MOD)%MOD){}  //コンストラクタ
  mint operator-() const { return mint(-x); } //符号変換
  mint operator+(const mint &a) const { return mint(*this) += a; } //算術演算子
  mint operator-(const mint &a) const { return mint(*this) -= a; }
  mint operator*(const mint &a) const { return mint(*this) *= a; }
  mint operator/(const mint &a) const { return mint(*this) /= a; }
  mint pow(ll n) const {  //繰り返し累乗
    if(!n) return 1;
    mint a = pow(n>>1);
    a *= a;
    if(n&1) a *= *this;
    return a;
  }
  mint inv() const { return pow(MOD-2); } // for prime mod
  mint& operator+=(const mint a){ if((x+=a.x) >= MOD) x-=MOD;  return *this; } //代入演算子
  mint& operator-=(const mint a){ if((x+=MOD-a.x) >= MOD) x-=MOD;  return *this; }
  mint& operator*=(const mint a){ (x *= a.x) %= MOD;  return *this; }
  mint& operator/=(const mint a){ return (*this) *= a.inv(); }
  friend ostream& operator<<(ostream &stout, const mint &tmp){ stout << tmp.x; return stout; }
};

int main(){
  cin.tie(0), ios::sync_with_stdio(false);
  int n,m; cin >> n >> m;
  if(2 <= abs(n-m)) cout << 0;
  else{
    mint ans = 0;
    if(abs(n-m) == 1) ans = 1;
    else ans = 2;
    rep(i,n) ans *= i+1;
    rep(i,m) ans *= i+1;
    cout << ans;
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 3632
//In the name of Allah
//In the name of the compassionate of the merciful
//Ya Ali!
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename Type>
using ordered_multiset = tree<Type, null_type, less_equal<Type>, rb_tree_tag, tree_order_statistics_node_update> ;

typedef long long ll ;
typedef long double ld ;

const ll maxn = 3011 ;
const ll INF = 3e18 ;

#define f first
#define s second
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define endll "\n"
#define sortt(v) sort(v.begin() , v.end())
#define reversee(v) reverse(v.begin() , v.end())

// for sqrt on interval and array , always sq = maxn/80 ;
// cout << *ss.find_by_order(index) ; -> return the value that indexed in index position
// cout << ss.order_of_key(value) ; -> lower_bound in ordered_set
//ifstream fin("input.txt");
//ofstream fout("output.txt");
// fflush(stdout);
ll mod = 1e9 + 7 , p1 = 999999929 , p2 = 999999937 ;

ll n , a[maxn] , dp[maxn][maxn][2] ;

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

cin >> n ;
for(int i = 1 ; i <= n ; i ++)cin >> a[i] ;

for(int i = 1 ; i <= n ; i ++){
 dp[i][i][0] = a[i] ;
 dp[i][i][1] = (-1)*a[i] ;
}

for(int r = 2 ; r <= n ; r ++){
  for(int l = r-1 ; l > 0 ; l --){
   dp[l][r][0] = max(dp[l+1][r][1]+a[l] , dp[l][r-1][1]+a[r]) ;
   dp[l][r][1] = min(dp[l+1][r][0]-a[l] , dp[l][r-1][0]-a[r]) ;
   //cout << a[l] << " " << l << endl ;
  }
}
cout << dp[1][n][0] ;

 return 0;
}
/*
                  _     _   __
            /_\  (_    (_)  __)
           /   \  _) . (_) (__
*/


Measured memory_bytes: 141568
import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        try (Scanner in = new Scanner(System.in)) {
            long N = in.nextInt();
            int M = in.nextInt();
            int[][] link = new int[M][2];
            for (int i = 0; i < M; i++) {
                link[i][0] = in.nextInt() - 1;
                link[i][1] = in.nextInt() - 1;
            }

            long[] n = new long[M + 1];
            int index = 0;
            n[index++] = (N * N - N) / 2;

            UnionFind uf = new UnionFind();
            uf.init((int) N);
            for (int i = M - 1; i >= 0; i--) {
                if (uf.find(link[i][0]) == uf.find(link[i][1])) {
                    n[index] = n[index - 1];
                    index++;
                    continue;
                }
                long size0 = uf.size(link[i][0]);
                long size1 = uf.size(link[i][1]);
                uf.unite(link[i][0], link[i][1]);
                n[index] = n[index - 1] - (size0 * size1);
                index++;
            }

            for (int i = n.length - 1 - 1; i >= 0; i--) {
                System.out.println(n[i]);
            }

        }
    }
}

class UnionFind {
    private int[] par;
    private int[] rank;
    private int[] size;

    public void init(int n) {
        par = new int[n];
        rank = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            par[i] = i;
            rank[i] = 0;
            size[i] = 1;
        }
    }

    public int find(int x) {
        if (par[x] == x) {
            return x;
        } else {
            int find = find(par[x]);
//            size[find] = size[par[x]];
            par[x] = find;
            return par[x];
        }
    }

    public int size(int x) {
        return size[find(x)];
    }

    public void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return;
        }
        if (rank[x] < rank[y]) {
            par[x] = y;
            size[y] += size[x];
        } else {
            par[y] = x;
            if (rank[x] == rank[y]) {
                rank[x]++;
            }
            size[x] += size[y];
        }
    }

    public boolean same(int x, int y) {
        return find(x) == find(y);
    }
}


Measured memory_bytes: 102212
package main

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

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)

	x, y := nextInt(), nextInt()

	count := 0

	for x <= y {
		x *= 2
		count++
	}

	fmt.Println(count)
}


Measured memory_bytes: 640
#include <iostream>


using namespace std;

int main()
{
    int A,B,S;
    char op;
    cin >> A >> op >>B;
    switch(op)
    {
    case'+':
    S = A + B;
    break;
    case'-':
    S = A - B;
    break;
    }
    cout << S << endl;
    return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

C = [0] * (N+1)
C[0] = 3

ans = 1
for a in A:
    ans *= C[a]
    ans %= MOD
    C[a] -= 1
    C[a+1] += 1
print(ans)


Measured memory_bytes: 14072
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <map>
#include <list>
#include <queue>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <stack>
#include <set>
#include <bitset>
#include <deque>
#pragma GCC optimize(3 , "Ofast" , "inline")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
using namespace std ;
#define ios ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define x first
#define y second
#define pb push_back
#define ls rt << 1
#define rs rt << 1 | 1
typedef long long ll ;
const double esp = 1e-6 , pi = acos(-1) ;
typedef pair<ll , ll> PII ;
const int N = 1e6 + 10 , INF = 0x3f3f3f3f , mod = 1e9 + 7;
ll a[5] , b[N] ;
int work()
{
  int n ;
  cin >> n ;
  for(int i = 0 ;i < 4 ;i ++ ) a[i] = -1e18 , b[i] = INF ;
  for(int i = 1; i <= n ;i ++ ) {
    ll x , y ;
    cin >> x >> y ;
    a[0] = max(a[0] , -x - y) ;
    a[1] = max(a[1] , -x + y) ;
    a[2] = max(a[2] , x + y) ;
    a[3] = max(a[3] , x - y) ;
    b[0] = min(b[0] , -x - y) ;
    b[1] = min(b[1] , -x + y) ;
    b[2] = min(b[2] , x + y) ;
    b[3] = min(b[3] , x - y) ;
  }
  ll ans = 0 ;
  for(int i = 0 ;i < 4 ; i ++ )
   ans = max(ans , a[i] - b[i]) ;
  cout << ans << endl ;
  return 0 ;
}
int main()
{
  //   freopen("C://Users//spnooyseed//Desktop//in.txt" , "r" , stdin) ;
  //   freopen("C://Users//spnooyseed//Desktop//out.txt" , "w" , stdout) ;

  work() ;
  return 0 ;
}
/*
*/


Measured memory_bytes: 3164
N, K = map(int,input().split())
S = input()
count_RL = 0
for i in range(N-1):
    if S[i] == 'R' and S[i+1] == 'L':
        count_RL += 1
count_edge = 0
if S[0] == 'L':
    count_edge += 1
if S[N-1] == 'R':
    count_edge += 1
count_K = 0
for i in range(K):
    if count_RL == 0:
        break
    count_RL -= 1
    count_K += 1
if (K - count_K) > 0:
    count = K - count_K
    if count_edge == 2:
        count_edge -= 1
if count_edge == 0 and count_RL == 0:
    count_edge = 1
    
not_happy = N - 2*count_RL - count_edge
print(not_happy)

Measured memory_bytes: 3316
num_x, num_y, num_z, k = map(int, input().split())

x_list = sorted(list(map(int, input().split())))
y_list = sorted(list(map(int, input().split())))
z_list = sorted(list(map(int, input().split())))

xy_list = sorted([x + y for x in x_list for y in y_list], reverse=True)[:k]
xyz_list = sorted([xy + z for xy in xy_list for z in z_list], reverse=True)[:k]

for xyz in xyz_list:
  print(xyz)

Measured memory_bytes: 185648