akhauriyash/Code-Regression huggingface dataset:
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		ArrayDeque<Comb> deq = new ArrayDeque<>();
		ArrayDeque<Comb> next = new ArrayDeque<>();
		deq.add(new Comb());
		for (int i = 0; i < n; i++) {
		    int x = sc.nextInt();
		    while(deq.size() > 0) {
		        Comb cc = deq.poll();
		        next.add(cc.addA(x));
		        next.add(cc.addB(x));
		        next.add(cc.addC(x));
		        next.add(cc);
		    }
		    ArrayDeque<Comb> tmp = next;
		    next = deq;
		    deq = tmp;
		}
		int min = Integer.MAX_VALUE;
		while (deq.size() > 0) {
		    Comb cc = deq.poll();
		    min = Math.min(min, cc.getPoint(a, b, c));
		}
		System.out.println(min);
	}
    
    static class Comb {
        int aLen;
        int bLen;
        int cLen;
        int point;
        
        public Comb(int aLen, int bLen, int cLen, int point) {
            this.aLen = aLen;
            this.bLen = bLen;
            this.cLen = cLen;
            this.point = point;
        }
        
        public Comb() {
            this(0, 0, 0, 0);
        }
        
        public Comb addA(int x) {
            int add = 0;
            if (aLen > 0) {
                add = 10;
            }
            return new Comb(aLen + x, bLen, cLen, point + add);
        }
        
        public Comb addB(int x) {
            int add = 0;
            if (bLen > 0) {
                add = 10;
            }
            return new Comb(aLen, bLen + x, cLen, point + add);
        }
        
        public Comb addC(int x) {
            int add = 0;
            if (cLen > 0) {
                add = 10;
            }
            return new Comb(aLen, bLen, cLen + x, point + add);
        }
        
        public int getPoint(int a, int b, int c) {
            if (aLen == 0 || bLen == 0 || cLen == 0) {
                return Integer.MAX_VALUE;
            }
            point += Math.abs(aLen - a) + Math.abs(bLen - b) + Math.abs(cLen - c);
            return point;
        }
    }
    	
}


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

clock_t present = clock();
void complexiti(){
	present = clock() - present;
	cerr << "TIME : " << float(present)/CLOCKS_PER_SEC << '\n';
}

int INF = (int)1 << 30;
vector<int> v;

void longestNonDecreasingSubsequenceSize(){
	int n = v.size();
	vector<int> arr(n,INF);
	for(auto i:v){
		*upper_bound(arr.begin() , arr.end() , i) = i;
	}
	cout << lower_bound(arr.begin() , arr.end() , INF) - arr.begin() << endl;
}

void solver(){
	//~ type your code here
	int n;
	cin >> n;
	v.resize(n);
	for(auto &i:v){
		cin >> i;
	}
	reverse(v.begin() , v.end());
	longestNonDecreasingSubsequenceSize();
	return;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int queries = 1;
	//~ cin >> queries;
	for(int i = 0 ; i < queries ; ++i){
		solver();
	}
	complexiti();
	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
 
using std::pair;
using std::vector;
using std::string;

typedef long long ll;
typedef pair<int, int> pii;
 
#define fst first
#define snd second
#define pb(a) push_back(a)
#define mp(a, b) std::make_pair(a, b)
#define debug(...) fprintf(stderr, __VA_ARGS__)
 
template <typename T> bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
 
const int oo = 0x3f3f3f3f;
 
template<typename T> T read(T& x) {
    int f = 1; x = 0;
    char ch = getchar();
    for(;!isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48; 
    return x *= f;
}

const int N = 100000;
const int M = 400000;
const int mo = 1e9 + 7;

int st[N + 5], to[M + 5], nxt[M + 5], w[M + 5], e = 1;

inline void addedge(int x, int y, int z) {
    to[++ e] = y;
    nxt[e] = st[x];
    st[x] = e; w[e] = z;
}

ll diss[N + 5], dist[N + 5];
bool vis[N + 5];

int n, m, S, T;
int cnts[N + 5], cntt[N + 5];
vector<int> pres[N + 5], pret[N + 5];

typedef pair<ll, int> pli;

void spfa(ll *dis, int *cnt, vector<int>* pre, int s) {
    std::priority_queue<pli, vector<pli>, std::greater<pli> > que;

    memset(vis, 0, sizeof vis);

    cnt[s] = 1;
    dis[s] = 0;
    que.push(mp(0, s));

    while(!que.empty()) {
        int x = que.top().snd; que.pop();
        if(vis[x]) continue;

        vis[x] = true;
        for(int i = st[x]; i; i = nxt[i]) {
            int y = to[i];
            if(vis[y]) continue;

            if(chkmin(dis[y], dis[x] + w[i])) {

                pre[y].clear();

                cnt[y] = cnt[x];
                pre[y].pb(x);
                que.push(mp(dis[y], y));

            } else if(dis[y] == dis[x] + w[i]) {

                cnt[y] = (cnt[x] + cnt[y]) % mo;
                pre[y].pb(x);
            }
        }
    }
}

int main() {
#ifdef Wearry
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif 

    read(n), read(m);
    read(S), read(T);

    for(int i = 1; i <= m; ++i) {
        static int x, y, z;
        read(x), read(y), read(z);
        addedge(x, y, z), addedge(y, x, z);
    }

    memset(diss, oo, sizeof diss);
    memset(dist, oo, sizeof dist);

    spfa(diss, cnts, pres, S);
    spfa(dist, cntt, pret, T);

    ll DIS = dist[S];
    ll ans = 1ll * cnts[T] * cntt[S] % mo;

    for(int i = 1; i <= n; ++i) {
        if(DIS % 2 == 0 && dist[i] == DIS / 2) {
            ans -= 1ll * cnts[i] * cnts[i] % mo * cntt[i] % mo * cntt[i] % mo;
            ans %= mo;
        } 
        if(diss[i] + dist[i] != DIS) continue;
        for(int j = 0; j < int(pret[i].size()); ++j) {
            int pre = pret[i][j];
            if(dist[pre] < DIS / 2 && dist[i] > (DIS+1) / 2) {
                ans -= 1ll * cntt[pre] * cntt[pre] % mo * cnts[i] % mo * cnts[i] % mo; 
                ans %= mo;
            }
        }
    }
    printf("%lld\n", (ans + mo) % mo);

    return 0;
}


Measured memory_bytes: 20308
#include <bits/stdc++.h>
using namespace std;
    
#define int long long int
#define vi vector<int>
#define vvi vector<vi>
#define read(a)  for(int i = 0; i < n; i++) cin >> a[i];
#define print(a)  for(int i = 0; i < n; i++) cout << a[i] << " ";
#define pb push_back
#define pql priority_queue<int>
#define pqs priority_queue<int, vi, greater<int>>
#define pqlv priority_queue<vi>
#define pqsv priority_queue<vi, vvi, greater<vi>>
#define endl '\n'
#define N 10000002
#define MOD 1000000007

signed main() {
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    int i = 0, j = 0;
    int ans = 0;
    while(j < n) {
        if(s[j] == '0') {
            while(j < n && s[j] == '0') j++;
            k--;
        }
        else {
            while(j < n && s[j] == '1') j++;
        }
        while(k < 0) {
            if(s[i] == '0') {
                while(i < n && s[i] == '0') i++;
                k++;
            }
            else {
                while(i < n && s[i] == '1') i++;
            }
        }
        ans = max(ans, j - i);
    }
    cout << ans << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define print(x)cout<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;

int main() {
  ll t1,t2;
  cin >> t1 >> t2;
  ll a1,a2,b1,b2;
  cin >> a1 >> a2 >> b1 >> b2;

  ll sumA = 0, sumB = 0;
  sumA+=a1*t1;
  sumB+=b1*t1;
  int flag1 = (sumA>=sumB);
  ll diff1 = sumA-sumB;
  sumA+=a2*t2;
  sumB+=b2*t2;
  int flag2 = (sumA>=sumB);
  ll diff2 = sumA-sumB;
  if(sumA == sumB){
    cout<<"infinity"<<endl;
  }
  else if(flag1 == flag2){
    cout<<0<<endl;
  }
  else{
    ll ans = 0;
    if(diff1%diff2) ans = diff1/diff2*2-1;
    else ans = diff1/diff2*2;
    cout<<abs(ans)<<endl;
  }

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#include <queue>
#include <set>
#include <iostream>
#include <iomanip>
using namespace std;
typedef long long LL;
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

int main(){
    int N;
    cin >> N;
    vector<LL> a(N);
    vector<LL> part_sum(N);
    LL tmp=0;
    REP(i,N){
        cin >> a[i];
        tmp += a[i];
        part_sum[i] = tmp;
    }

    LL all_sum = part_sum[N-1];
    LL val = abs(all_sum - 2*part_sum[0]);
    REP(i,N-1){
        LL tmp = abs(all_sum - 2*part_sum[i]);
        chmin(val, tmp);
    }

    cout << val << endl;
    return 0;

}

Measured memory_bytes: 6408
#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,n) for(ll i=a;i<n;i++)
#define ALL(s) s.begin(),s.end()
#define P pair<ll,ll>
#define vl vector<ll>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvl vector<vector<ll>>
#define print(n) cout<<n<<endl
const int M=100010;
const int inf=1000000007;
const long long INF=1000000000000000007;
using ll=long long;
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};


int main(){
	int p,q,r;
	cin>>p>>q>>r;
	int ans=inf;
	ans=min({p+q,p+r,q+r});
	print(ans);
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <numeric>

using namespace std;

int main(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    int r=0;
    int b=0;
    for(int i=0;i<n;i++){
        if(s[i]=='R')r++;
        else b++;
    }
    if(r>b)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    
}

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

using namespace std;
using ll = long long;

using Field = vector<vector<int>>;
using Graph = vector<vector<int>>;
using VI = vector<int>;
using VC = vector<char>;
using PI = pair<int, int>;

#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) x.begin(), x.end()

const long long INF = 1LL<<60;
const int mod = 1000000007;

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

ll X;

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

    cin >> X;

    ll year = 0;
    ll money = 100;

    while (money < X) {
        money *= 1.01;
        year++;
    }

    cout << year << endl;
    
    return 0;
}

Measured memory_bytes: 3636
import sys
import itertools
from collections import defaultdict, deque
from copy import deepcopy
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N = I()
    P = LI()
    Q = LI()
    index = 1
    seq = [i+1 for i in range(N)]
    for i in itertools.permutations(seq, r=None):
        if P == i:
            a = index
        if Q == i:
            b = index        
        index += 1
    print(abs(a-b))

if __name__ == "__main__":
    main()

Measured memory_bytes: 73316
#include<stdio.h>
int main(void)
{
	int r,g,b,x;
	scanf("%d %d %d",&r,&g,&b);
	x=r*100+g*10+b*1;
	if(x%4==0){
			printf("YES\n");
	}
	else printf("NO\n");
	return 0;
}

Measured memory_bytes: 128
#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<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 998244353;
const ll INF = mod * mod;
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 pair<ll, ll> LP;
typedef vector<LP> vec;
typedef vector<string> svec;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-8;

ll sum[501][501];
ll dp[502][502];
ll cop[502][502];

ll sum2[501][501];


void solve() {
	int n; cin >> n;
	vector<vector<ll>> a(n);
	rep(i, n) {
		a[i].resize(n);
		rep(j, n) {
			if (i == j)a[i][j] = 0;
			else cin >> a[i][j];
		}
	}

	//calc sum
	rep(i, n) {
		ll s = 0;
		for (int j = i + 1; j < n; j++) {
			for (int k = i; k < j; k++) {
				s += a[k][j];
			}
			sum[i][j] = s;
		}
	}
	rep(i, n) {
		ll s = 0;
		for (int j = n - 1; j >= i; j--) {
			sum2[i][j] = s;
			s += a[j][i];
		}
	}

	rep(i, n + 1)rep(j, n + 1)dp[i][j] = INF;
	dp[0][0] = 0;
	{
		ll s = 0;
		for (int j = n-1; j>0; j--) {
			for (int k = 0; k <= j; k++) {
				dp[j][k] = s + sum[0][k] + sum[k + 1][j];
			}

			s += a[j][0];
		}
	}
	for (int i = 1; i < n-1; i++) {
		rep(j, n + 1)rep(k, n + 1)cop[j][k] = INF;

		for (int k = i; k < n; k++) {
			ll mi = INF;
			for (int l = k; l <n; l++) {
				mi = min(mi, dp[l][k] - sum[k + 1][l]);
				cop[l][k] = sum2[i][l] + sum[k + 1][l] + mi;
			}
		}
		ll mi = INF;
		for (int m = i; m < n; m++) {
			mi = min(mi, dp[m][i - 1] - sum[i][m]);
			for (int l = m; l < n; l++) {
				cop[l][m] = min(cop[l][m], sum2[i][l] + sum[i][m] + sum[m + 1][l] + mi);
			}
		}
		rep(j, n + 1)rep(k, n + 1)dp[j][k]=cop[j][k];

	}
	ll ans = INF;
	rep(i, n+1)rep(j, n+1)ans = min(ans, dp[i][j]);
	cout << ans << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//init();
	solve();
	//cout << "finish" << endl;
	//stop
	return 0;
}


Measured memory_bytes: 10112
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
int main()
{
  // ios_base::sync_with_stdio(0);
  // cin.tie(0);
  // cout.tie(0);
  ll happiness[3];
  ll n,a,b,c,i,j,k;
  cin>>n;
  vector<ll>arr[n];
  for(i=0;i<n;i++)
  {
    cin>>a>>b>>c;
    arr[i].push_back(a);
    arr[i].push_back(b);
    arr[i].push_back(c);
  }
  for(i=0;i<3;i++)
  {
    happiness[i]=0;
  }
  if(n>1)
  {
    for(i=n-2;i>=0;i--)
    {
      for(j=0;j<3;j++)
      {
        for(k=0;k<3;k++)
        {
          if(j!=k)
          {
            happiness[j]=max(arr[i+1][k]+arr[i][j],happiness[j]);
          }
        }
        arr[i][j]=happiness[j];
      }
    }
  }
  else
  {
    for(i=0;i<3;i++)
    {
      happiness[i]=arr[0][i];
    }
  }
  
  cout<<*max_element(happiness,happiness+3)<<endl;

}
  

Measured memory_bytes: 10616
#include <bits/stdc++.h>
using namespace std;
#define NewNode (ListNode *)malloc(sizeof(ListNode))
#define Mem(a,b) memset(a,b,sizeof(a))
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-10;
const unsigned long long mod = 998244353;
const double II = 3.1415926535;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> piil;
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,m,sum = 0;
    cin >> n >> m;
    int vis[n+5] = {0},h[n+5] = {0};
    for(int i = 1;i <= n;i++) cin >> h[i];
    for(int i = 1;i <= m;i++)
    {
        int a,b;
        cin >> a >> b;
        if(h[a] > h[b]) vis[b] = 1;
        else if(h[a] == h[b]) vis[a] = 1,vis[b] = 1;
        else vis[a] = 1;
    }
    for(int i = 1;i <= n;i++)
        if(!vis[i])
            sum++;
    cout << sum << endl;
}


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

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

    int n;
    cin >> n;
    for (int i=1; i<=9; i++){
        for (int j=1; j<=9; j++){
            if (i*j == n){
                cout << "Yes\n";
                return 0;
            }
        }
    }
    cout << "No\n";
}

Measured memory_bytes: 256
N = int(input())
A = []
B = []
for i in range(N):
  A.append(int(input()))
  
A.sort()
B.append(1)

for i in range(1, N):
  if(A[i]!= A[i- 1]):
    B.append(1)
  else:
    B[-1]+= 1
  i+= 1
  
ans = list(filter(lambda x: x % 2 == 1, B))

print(len(ans))

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

int cnt=0;
int N;
string P,Q;
int qcnt=0,pcnt=0;

void dfs(string st, string sm){
  // basic pattern  
  if(sm.size()==N){
    cnt++;
    if(sm==Q)
      qcnt=cnt;
    if(sm==P)
      pcnt=cnt;
    
    return;
  }
  
  // recursive pattern
  for(int i=0;i<st.size();i++){
    string swk=st;
    swk.erase(i,1);
    dfs(swk,sm+st.at(i));
  }
}



int main() {
  cin>>N;
  
  for(int i=0;i<N;i++){
    char cwk;
    cin>>cwk;
    P+=cwk;
  }
  for(int i=0;i<N;i++){
    char cwk;
    cin>>cwk;
    Q+=cwk;
  }
  string s;
  for(int i=1;i<N+1;i++){
    s+=(char)('0'+i);
  }
  dfs(s,"");
  
  cout<<abs(qcnt-pcnt)<<endl;
  
  return 0;
}

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

using namespace std;

int GCD(int a, int b)
{
    int r = a%b;
    while(r)
    {
        a = b;
        b = r;
        r = a%b;
    }
    return b;
}

int main(void)
{
    int N, i, j, k; 
    unsigned long long out = 0;
    cin >> N;
    int gcd[201][201];

    for(i = 1; i <= N; i++)
    {
        gcd[i][i] = i;
        for(j = i+1; j <= N; j++)
        {
            gcd[i][j] = GCD(j, i);
            gcd[j][i] = gcd[i][j];
        }
    }

    for(i = 1; i <= N; i++)
    {
        for(j = 1; j <= N; j++)
        {
            for(k = 1; k <= N; k++)
            {
                out += gcd[i][gcd[j][k]]; 
            }
        }
    }
    cout << out <<endl; 
    return 0;
}


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

using namespace std;

int main()
{
    map <string,int> m;
    int q;
    cin>>q;
    while(q--)
    {
        int a;
        cin>>a;
        if(a==0)
        {
            string key;
            long long x;
            cin>>key>>x;
            m[key]=x;
        }
        else if(a==1)
        {
            string key;
            cin>>key;
            if(m.count(key))
                cout<<m[key]<<endl;
            else
                cout<<"0"<<endl;
        }
        else if(a==2)
        {
            string key;
            cin>>key;
            m.erase(key);
        }
        else
        {
            string l,r;
            cin>>l>>r;
            auto p=m.lower_bound(l);
            while(p!=m.end()&&p->first<=r)
            {
                cout<<p->first<<" "<<p->second<<endl;
                p++;
            }
        }
    }
    return 0;
}



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

int main() {
  string N;
  cin >> N;
  int X = stoi(N);
  int fX;
  for(int i=0; i<N.size(); i++) {
   fX += (int)(N.at(i) - '0');
  }
  if(X % fX == 0) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 3628
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;
typedef string::const_iterator State;
#define Ma_PI 3.141592653589793
#define eps 1e-5
#define LONG_INF 2000000000000000000LL
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL
#define MOD 998244353LL
#define seg_size 262144
#define REP(a,b) for(long long a = 0;a < b;++a)
int main(){
	int x;
	cin >> x;
	cout << x * x << endl;
}


Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
using LL  = long long;
using VI  = vector<LL>;
using VVI = vector<VI>;
using VB  = vector<bool>;
using VS  = vector<string>;
using PII = pair<LL, LL>;
using VP  = vector<PII>;
#define PB           push_back
#define MP           make_pair
#define SZ(a)        LL((a).size())
#define EACH(x, c)   for (auto x : (c))
#define ALL(c)       (c).begin(), (c).end()
#define REVERSE(c)   reverse(ALL(c))
#define SORT(c)      stable_sort(ALL(c))
#define RSORT(c)     stable_sort((c).rbegin(), (c).rend())
#define FSORT(c)     stable_sort(ALL(c), [] (auto& x, auto& y) {return x.first < y.first;});
#define FRSORT(c)    stable_sort(ALL(c), [] (auto& x, auto& y) {return x.first > y.first;});
#define SSORT(c)     stable_sort(ALL(c), [] (auto& x, auto& y) {return x.second < y.second;});
#define SRSORT(c)    stable_sort(ALL(c), [] (auto& x, auto& y) {return x.second > y.second;});
#define FOR(i, a, b) for (LL i = (a); i < (b); ++i)
#define REP(i, n)    FOR(i, 0, n)
#define $(x) {cout << #x << " = " << (x) << endl;}


int main() {
    LL N, W;
    cin >> N >> W;
    VI w(N + 1), v(N + 1);
    FOR(i, 1, N + 1) cin >> w[i] >> v[i];

    VVI dp(N + 1, VI(W + 1));   // dp[i][j] := max sum of w using 1,...,i objects s.t. sum of w <= j
    FOR(i, 0, N) {
        REP(j, W + 1) {
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
            if (j + w[i + 1] <= W) {
                dp[i + 1][j + w[i + 1]] = max(dp[i + 1][j + w[i + 1]], dp[i][j] + v[i + 1]);
            }
        }
    }

    cout << dp[N][W] << endl;

    return 0;
}


Measured memory_bytes: 80256
IDENTIFICATION DIVISION.
PROGRAM-ID. PROGRAM_ID.

DATA DIVISION.
WORKING-STORAGE SECTION.
01 LN     PIC X(3).
01 a      PIC 9(1).
01 b      PIC 9(1).
01 n      PIC 9(1).
01 i      PIC 9(2).
01 ans    PIC X(9).

PROCEDURE DIVISION.
  ACCEPT LN.
  UNSTRING LN DELIMITED BY SPACE INTO a b.
  IF a < b
      MOVE b TO n
  ELSE
      MOVE a TO n
      MOVE b TO a
  END-IF.
  PERFORM VARYING i FROM 1 BY 1 UNTIL n < i
      MOVE a TO ans(i:1)
  END-PERFORM.
  DISPLAY ans(1:n).
  STOP RUN.


Measured memory_bytes: 888
/*
 ╔═══╦═══╦═══╗
 ║╔═╗║╔══╩╗╔╗║
 ║║░║║╚══╗║║║║
 ║║░║║╔══╝║║║║
 ║╚═╝║╚══╦╝╚╝║
 ╚══╗╠═══╩═══╝
 ░░░╚╝░░░░░░░░
 */

#include <bits/stdc++.h>
#define ll					long long
#define MOD					1000000007
#define MAX					1e9
#define MIN                 -1e9
#define PI					acos(-1.0)
#define vi					vector<int>
#define vii					vector<vi>
#define vll					vector<ll>
#define mid(s,e)			(s+(e-s)/2)
#define clz(n)				__builtin_clzll(n))

using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
template<typename T>
void printVec(const T &v, char sep=' ') {for (auto &i: v) cout << i << sep;}
template<typename T>
void printVecPair(const T &v, char sep=' ') {for (auto &i: v) cout << i.first <<" " << i.second<< sep;}


#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

int main() {
	ios::sync_with_stdio(false);
 	cin.tie(0);
	int n; scanf("%d",&n);
	int a[110000];
	for(int i=0;i<n;i++) scanf("%d",a+i);
	for(int i=n-2;i>=0;i--) {
			if(a[i] > a[i+1]) {
					a[i]--;
					if(a[i] > a[i+1]) {
							cout<<"No";
							return 0;
					}
			}
	}
	cout<<"Yes";
	return 0;
}





Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(ll i=0;i<n;i++)
const ll INF=1e15;
const ll MOD=1000000007;

ll dp[3005][3005];
int main(){
    ll N,T;cin>>N>>T;
    pair<ll,ll> val[N];
    rep(i,N)cin>>val[i].first>>val[i].second;
    sort(val,val+N);
    ll ans=0;
    rep(i,N-1)rep(j,T){
        if(j<val[i].first)dp[i+1][j]=dp[i][j];
        else dp[i+1][j]=max(dp[i][j],dp[i][j-val[i].first]+val[i].second);
        ans=max(ans,dp[i+1][T-1]+val[i+1].second);
    }
    cout<<ans<<endl;
    return 0;
}

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

void show(int arr[], int N){
	for(int i=0; i<N; i++)
		if(i<N-1)
			cout<<arr[i]<<' '<<flush;
		else
			cout<<arr[i]<<flush;
	cout<<endl;
}


void swap(int& a, int& b){
	int t=a;
	a=b;
	b=t;
}


int ShellSort(int* arr, int N);
int InsertionSort_r(int* arr, int N, int r);

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

	int* arr= new int[N];

	for(int i=0; i<N; i++)
		cin>>arr[i];

	int count=ShellSort(arr, N);

	cout<<count<<endl;

	for( int i=0; i<N; i++)
		cout<<arr[i]<<endl;

	delete[] arr;
}


int ShellSort(int* arr, int N)
{
	int counter=0;




	int* range= new int[N];  //range= { 1, 4, 13, 40 ...}


	range[0] = 1;

	int i;
	for( i=1; range[i-1]*3+1 < N; i++){
		range[i] = range[ i-1 ]*3+1;
	}
	int range_len =i; //range ?????????????????§????????\??£????????????

	
	cout<<range_len<<endl;

	for( int i=1; range_len - i >=0; i++ )
		cout<<range[ range_len - i ]<<' '<<flush;
	cout<<endl;







	 

	for( int i=0; range_len -i -1 >=0; i++) 
		counter=InsertionSort_r(arr, N, range[ range_len - i -1 ]);
	
	
	return counter;

	delete[] range;
	
	



	
}

int InsertionSort_r(int arr[], int N, int r)
{

	static int counter=0;
	int compindex;
	int comp;
	int j;

	
	for( int i=0; i<r; i++) {


		for( int compindex=N- r -1 -i; compindex> -1; compindex-=r ){
			
			comp=arr[compindex];
			j=r;
			for( ; compindex+j<N; j+=r ){

				if(comp > arr[compindex+j]){
					arr[compindex + j -r] = arr[compindex + j];
					counter++;
				}
				else
					break;
				
			}
			arr[compindex + j - r] = comp;

		


		}
	}


	return counter;



	
}

Measured memory_bytes: 4896
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define FAST_IO  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mod 100000
#define endl "\n"
#define PI 3.14159265358979323846264338327950288
 
using namespace std ;
using bigint = long long int ;
using vi = vector<int> ;
using vll = vector<long long int> ;

char ch[1003][1003] ;
bool visited[1004][1003] ;
int dist[1003][1003] ;
int N , M ;
bool isValid( int x , int y ){
    if( x > N || y > M || x < 1 || y < 1 || visited[x][y] || ch[x][y] == '#' )
        return false ;
    return true ;
}

void bfs( int x , int y ){
    deque<pair<int, int>> d ;
    dist[x][y] = 0 ;
    d.push_back({ x , y}) ;
    visited[x][y] = 1 ;
    
    while( !d.empty() ){
        pair<int, int> p = d.front() ;
        d.pop_front() ;
        int X = p.first , Y = p.second ;
        
        for( int i = -2 ; i <= 2 ; i++ ){
            for( int j = -2 ; j <= 2 ; j++ ){
                if( i == 0 && j == 0 )
                    continue ;
                int D = 1 ;
                if( ( abs(i) == 1 && abs(j) == 0 ) || ( abs(i) == 0 && abs(j) == 1 ) )
                    D = 0 ;
                if( dist[X+i][Y+j] > dist[X][Y] + D && isValid(X + i, Y + j) ){
                    dist[X+i][Y+j] = dist[X][Y] + D ;
                    if( D == 0 )
                        d.push_front({ X + i , Y + j}) ;
                    else
                        d.push_back({ X + i , Y + j }) ;
                }
            }
        }
    }
}

int main(){
    FAST_IO ;
    cin >> N >> M ;
    int srcX , srcY , destX , destY ; cin >> srcX >> srcY >> destX >> destY ;
    for( int i = 1 ; i <= N ; i++ ){
        for( int j = 1 ; j <= M ; j++ ){
            cin >> ch[i][j] ;
        }
    }
    for( int i = 1 ; i <= N ; i++ ){
        for( int j = 1 ; j <= M ; j++ ){
            dist[i][j] = 1e9 ;
        }
    }
    bfs(srcX, srcY) ;
    if( dist[destX][destY] != 1e9 )
        cout << dist[destX][destY] << endl ;
    else
        cout << "-1" << endl ;
    
    return 0 ;
}
 

Measured memory_bytes: 8576
#include <bits/stdc++.h>
#define maxn 100086

using namespace std;

int n, k;
int x, y;
vector<int> v[maxn];
int a[maxn];
bool vis[maxn];

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > q;

int main(){
	scanf("%d", &n);
	for(int i = 1;i < n;i++){
		scanf("%d%d", &x, &y);
		v[x].push_back(y), v[y].push_back(x);
	}
	scanf("%d", &k);
	while(k--){
		scanf("%d%d", &x, &y);
		a[x] = y;
		vis[x] = true;
		q.push({y, x});
	}
	while(!q.empty()){
		pair<int, int> p = q.top();q.pop();
		x = p.second;
		for(int i = 0;i < v[x].size();i++){
			int to = v[x][i];
			if(!vis[to]){
				a[to] = a[x] + 1;
				q.push({a[to], to});
				vis[to] = true; 
			}else if(abs(a[to] - a[x]) != 1) return printf("No"), 0;
		}
	}
	puts("Yes");
	for(int i = 1;i <= n;i++) printf("%d\n", a[i]);
}

Measured memory_bytes: 10632
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
	int n;
	cin>>n;
	int x=n;
	int sum=0;
	while(n>0){
		sum+=n%10;
		n/=10;
	}
	if(x%sum!=0){
		cout<<"No"<<endl;
	}
	else{
		cout<<"Yes"<<endl;
	}
}

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

using namespace std;

typedef long long ll;

const ll MAX_CNT = 1000000;

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  ll d, g; cin >> d >> g;
  ll p[d+1], c[d+1], all[d+1];
  for(int i=1;i<=d;i++){
    cin >> p[i] >> c[i];
    all[i] = 100*i*p[i] + c[i];
  }
  ll mincnt = MAX_CNT;
  // 下からj桁目が1のときに100*(j+1)点問題をコンプリート
  for(int i=0;i<(1 << (d+1));i++){
    ll sum = 0, cnt = 0;
    ll maxd = 0;
    for(int j=0;j<d;j++){
      if(i & (1 << j)){
        sum += all[j+1];
        cnt += p[j+1];
      }else{
        maxd = j+1;
      }
    }
    if(sum >= g){
      mincnt = min(mincnt, cnt);
    }else{
      ll adder;
      if((g - sum) % (100 * maxd) == 0){
        adder = (g - sum) / (100 * maxd);
      }else{
        adder = (g - sum) / (100 * maxd) + 1;
      }
      if(adder < p[maxd]){
        mincnt = min(mincnt, adder + cnt);
      }
    }
  }
  cout << mincnt << endl;
}

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

#define Q int t; scanf("%d", &t); for(int q=1; q<=t; q++)
typedef long long int lli;
typedef pair<lli, lli> pi;


int main()
{
    lli x;
    cin >> x;
    lli ox = 100;
    double r=1.01;
    int i = 1;
    for(;; i++){
        ox *= r;
        if(ox >= x){
            break;
        }
    }
    cout << i << "\n";

    return 0;
}


Measured memory_bytes: 3620
import java.io.*;
import java.util.*;

public class Main{
	public static void main(String[] args) throws Exception{
		PrintWriter pw=new PrintWriter(System.out);
		MScanner sc = new MScanner(System.in);
		HashSet<String>set=new HashSet<>();
		int n=sc.nextInt();
		while(n-->0)set.add(sc.nextLine());
		pw.println(set.size());
		pw.flush();
	}
	static class MScanner {
		StringTokenizer st;
		BufferedReader br;
		public MScanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}
 
		public MScanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int[] intArr(int n) throws IOException {
	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public long[] longArr(int n) throws IOException {
	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public int[] intSortedArr(int n) throws IOException {
	        int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        shuffle(in);
	        Arrays.sort(in);
	        return in;
		}
		public long[] longSortedArr(int n) throws IOException {
	        long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        shuffle(in);
	        Arrays.sort(in);
	        return in;
		}
		public Integer[] IntegerArr(int n) throws IOException {
	        Integer[]in=new Integer[n];for(int i=0;i<n;i++)in[i]=nextInt();
	        return in;
		}
		public Long[] LongArr(int n) throws IOException {
	        Long[]in=new Long[n];for(int i=0;i<n;i++)in[i]=nextLong();
	        return in;
		}
		public String nextLine() throws IOException {
			return br.readLine();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
 
		public char nextChar() throws IOException {
			return next().charAt(0);
		}
 
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public boolean ready() throws IOException {
			return br.ready();
		}
 
		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
	static void shuffle(int[]in) {
		for(int i=0;i<in.length;i++) {
			int idx=(int)(Math.random()*in.length);
			int tmp=in[i];
			in[i]=in[idx];
			in[idx]=tmp;
		}
	}
	static void shuffle(long[]in) {
		for(int i=0;i<in.length;i++) {
			int idx=(int)(Math.random()*in.length);
			long tmp=in[i];
			in[i]=in[idx];
			in[idx]=tmp;
		}
	}
	static String arrToString(int[]x) {
		return Arrays.toString(x);
	}
	static String arrToString(long[]x) {
		return Arrays.toString(x);
	}
	static String arrToString(Integer[]x) {
		return Arrays.toString(x);
	}
	static String arrToString(Long[]x) {
		return Arrays.toString(x);
	}
}

Measured memory_bytes: 66264
// #include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
using namespace std;

typedef long long ll;
typedef long double ld;

#define alpha ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define ff first
#define ss second
#define fr(i,a,b) for(ll i=a; i<b; i++)
#define fr1(i,a,b) for(ll i=a; i>=b; i--)
#define input(arr,n) fr(i,0,n) cin>>arr[i]
#define output(arr,n) fr(i,0,n) cout<<arr[i]<<" "
#define min3(a, b, c) min(a,min(b, c))
#define min4(a, b, c, d) min(a, min(b, min(c, d)))
#define max3(a, b, c) max(a,max(b, c))
#define max4(a, b, c, d) max(a, max(b, max(c, d)))
#define vi vector<ll>
#define vii vector<pair<ll, ll> >
#define fixd(x) cout<<fixed<<setprecision(x);

#define dbg(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << '\n'
void err(istringstream *iss) {}
template<typename T, typename ... Args> void err(istringstream *iss, const T &_val, const Args & ... args) {
    string _name;
    *iss >> _name;
    if (_name.back()==',') _name.pop_back();
    cerr << _name << " = " << _val << "; ", err(iss, args ...);
}

const ld PI = acosl(-1.0);

//"Focus" on constraints.


void solve(){
	string s,t;
	cin>>s>>t;
	ll n=s.length();
	ll cnt=0;
	fr(i,0,n){
		if(s[i]!=t[i]) cnt++;
	}
	cout<<cnt<<"\n";
}

int main(){
	alpha

	ll t=1;
	// cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

Measured memory_bytes: 3624
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

s=SI()
if s[0]==s[1]==s[2]=="S":
    print(0)
    sys.exit()
count=0
if s[0]==s[1]=="R":
    count+=1
if s[1]==s[2]=="R":
    count+=1
print(count+1)
    
            
            

Measured memory_bytes: 67024
#include <stdio.h>

int main(){
  double num[12]={0};
  char str[12];
  
  double y=0;
  int n,i;
  
  scanf("%d",&n);
  
  for(i=0;i<n;i++){
  scanf("%lf %s",&num[i],str);
    if(str[0]=='J'){
    y=y+num[i];
    }
    else{
    y=y+(num[i]*380000);
    }
  }
  
 
  printf("%f",y);
  
  return 0;
}

Measured memory_bytes: 128
def the_sieve_of_eratosthenes(i):
    s = [j for j in range(2, i + 1)]
    j = 0
    while True:
        if j >= i - 3:
            for k in range(len(s) - 1, 0, -1):
                if s[k] == 0:
                    del s[k]
            return s
        if s[j] != 0:
            for k in range(2 * s[j] - 2, i - 1, s[j]):
                s[k] = 0
        j += 1

n = int(input())
p = the_sieve_of_eratosthenes(10 ** 3 + 9)
c = [0] * len(p)
j = 0
for i in range(2, n + 1):
    if i == p[j]:
        c[j] += 1
        j += 1
    else:
        k = 0
        m = i
        while True:
            if m == 1:
                break
            if m % p[k] == 0:
                c[k] += 1
                m /= p[k]
            else:
                k += 1
ans = 1
for i in c:
    ans *= i + 1
    if ans >= 10 ** 9 + 7:
        ans %= 10 ** 9 + 7
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define len(v) ll(v.size())
#define fi first
#define se second

template <class T>
void cout_vec(const vector<T> &vec){
  for(auto itr:vec) cout<<itr<<' ';
  cout<<'\n';
}

typedef pair<ll,ll> P;
const ll mod=1e9+7;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string x;
    cin>>x;
    ll n=len(x);
    ll now=0;
    ll cnt=0;
    rep(i,n){
      if(x[i]=='S') now++;
      if(x[i]=='T' && now!=0){
        cnt++;
        now--;
        //if(i+1<=n-1 && x[i+1]=='S') now=0;
      }
    }
    cout<<n-2*cnt<<endl;
}

Measured memory_bytes: 720
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define ull unsigned long long
using namespace std;
const int maxx = 1002;
const ll mod = 1e9 + 7;
const ll base = 311;
const ll base1 = 113;
const ll maxn = 1e6 + 7;
bool check;
ll t, T, n, a[maxn], b[maxn], m1, m, tong, r, ans, mx, k, f[maxn], ma[maxx][maxx], pw[maxn];
//ll , c[maxx], st1[maxx];
//ll  , pw[maxx];
//string s[maxx], ss[maxx], str, f[maxx][10];
struct dang
{
    ll mn, gcd, val, pos, dd;
};
string s;
struct les
{
    bool operator()(ll x, ll y)
    {
        return x > y;
    }
};
dang c[maxn];
deque<ll> st;
priority_queue<ll, vector<ll>, les >st1;
map<ll, ll> mp;
vector<ll> adj;
bitset<50> fa;
ll tinh(ll i, ll j)
{
    return (f[j] - f[i-1]*pw[j-i+1] + mod * mod)%mod;
}
void sol()
{
    cin >> n >> s;
    ans = 0;
    s = " " + s;
    pw[0] = 1;
    for(int i = 1; i <= n / 2; i ++)
    {
        pw[i] = (pw[i-1] * base)%mod;
    }
    for(int i = 1; i <= n; i ++)
    {
        f[i] = (f[i-1] * base + s[i] - 'a' + 1) % mod;
    }
    ll lf = 0, rt = n / 2, mid;
    while(lf <= rt)
    {
        mid = (lf + rt) / 2;
        check = false;
        for(int i = 1; i <= n - mid; i ++)
        {
            for(int j = i + mid; j <= n - mid + 1; j ++)
            {
                if(tinh(i, i + mid - 1) == tinh(j, j + mid - 1))
                {
                    check = true;
                    break;
                }
            }
        }
        if(check)lf = mid + 1;
        else rt = mid - 1;
    }
    cout << rt;
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    //freopen("Test.INP", "r", stdin);
    sol();
}


Measured memory_bytes: 6400
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  int n;
  cin >> n;
  vector<ll> v(n);
  rep(i, 0, n) cin >> v[i];
  sort(v.begin(), v.end());

  ll ans = 1;
  ll key = 1000000000000000000;
  rep(i, 0, n) {
    string a = to_string(ans);
    string b = to_string(v[i]);
    int dig = a.size()+b.size()-1;

    ans *= v[i];
    if (ans > key||(dig>=19&&ans!=key)) {
      cout << -1 << endl;
      return 0;
    }
  }
  cout << ans << endl;
}


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

#define N 100

int main(void) {
    int n, u, k, v;
    int A[N + 1][N + 1] = {};
    
    cin >> n;
    
    for(int i = 0; i < n; ++i) {
        cin >> u >> k;
        for(int j = 0; j < k; ++j) {
            cin >> v;
            A[u][v] = 1;
        }
    }
    
    for(int i = 1; i <= n; ++i) {
        cout << A[i][1];
        for(int j = 2; j <= n; ++j) {
            cout << ' ' << A[i][j];
        }
        cout << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3132
MAX = 10**6

N = gets.chomp.to_i
as = gets.chomp.split.map(&:to_i)

as.sort!
as << 0

arr = [true] + [false] * MAX

ans = []
0.upto(as.size - 1) do |i|
  next if arr[as[i]]

  unless i == as.size - 1
    as[i].step(MAX, as[i]) { |j| arr[j] = true }
  end

  ans << as[i] if as[i] != as[i + 1]

end

puts ans.size

Measured memory_bytes: 47548
v, e = map(int, input().split()) # 頂点数vと辺数eを入力

g = [[] for i in range(v)] # グラフの要素数を確保

for i in range(e):
 s, t = map(int, input().split()) 
 g[s].append(t) # グラフに辺を挿入


color = ['WHITE' for i in range(v)] # 全て未探索

def dfs(u):
 color[u] = 'GRAY'

 for adj in g[u]:
  if color[adj] == 'GRAY':
   return 1
  elif color[adj] == 'WHITE':
   if dfs(adj) == 1:
    return 1

 color[u] = 'BLACK'
 return 0

ans = 0
for u in range(v):
 color[i in range(v)] = 'WHITE'
 if dfs(u) == 1:
  ans = 1
  break

print(ans)


Measured memory_bytes: 5608
import sys
from operator import itemgetter 
readline = sys.stdin.readline

def compress(L):
    L2 = list(set(L))
    L2.sort()
    C = {v : k for k, v in enumerate(L2)}
    return L2, C

class Segtree:
    def __init__(self, A, intv, initialize = True, segf = max):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
        
    def update(self, k, x):
        k += self.N0
        self.data[k] = x
        while k > 0 :
            k = k >> 1
            self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])
    
    def query(self, l, r):
        L, R = l+self.N0, r+self.N0
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
    
    def binsearch(self, l, r, check, reverse = False):
        L, R = l+self.N0, r+self.N0
        SL, SR = [], []
        while L < R:
            if R & 1:
                R -= 1
                SR.append(R)
            if L & 1:
                SL.append(L)
                L += 1
            L >>= 1
            R >>= 1
        
        if reverse:
            for idx in (SR + SL[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx+1]):
                    idx = 2*idx + 1
                else:
                    idx = 2*idx
            return idx
        else:
            for idx in (SL + SR[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx]):
                    idx = 2*idx
                else:
                    idx = 2*idx + 1
            return idx

N = int(readline())
XL = [tuple(map(int, readline().split())) for _ in range(N)]
LR = [(x-l, x+l) for x, l in XL]

M = 2*N+1
inf = 1<<31
S = set([-inf])
for l, r in LR:
    S.add(l)
    S.add(r)
_, Cs = compress(list(S))
LR = [(Cs[l], Cs[r]) for l, r in LR]


table = [-inf]*M
for l, r in LR:
    table[r] = max(table[r], l)
dp = Segtree([None]*M, -inf, initialize = False, segf = max)
dp.update(0, 0)
for r in range(1, M):
    if table[r] == -inf:
        continue
    l = table[r]
    k = dp.query(0, l+1)
    dp.update(r, 1+k)

print(dp.query(0, M))


Measured memory_bytes: 100784
fun main(args: Array<String>) {
    var (N, K) = readLine()!!.split(" ").map(String::toInt)
    val xx = readLine()!!.split(" ").map(String::toInt)
    var pos = mutableListOf<Int>()
    var neg = mutableListOf<Int>()
    for (x in xx) {
        when {
            x == 0 -> K--
            x > 0 -> pos.add(x)
            else -> neg.add(-x)
        }
    }
    if (K == 0) {
        println(0)
        return
    }
    neg.reverse()
    var ans = 1 shl 29
    for (i in 0 until pos.size) {
        val d = pos[i]
        val rest = K - (i + 1)
        if (rest < 0) break
        if (rest == 0) ans = Math.min(ans, d)
        else if (rest <= neg.size) {
            ans = Math.min(ans, d * 2 + neg[rest-1])
        }
    }
    var tmp = pos; pos = neg; neg = tmp;
    for (i in 0 until pos.size) {
        val d = pos[i]
        val rest = K - (i + 1)
        if (rest < 0) break
        if (rest == 0) ans = Math.min(ans, d)
        else if (rest <= neg.size) {
            ans = Math.min(ans, d * 2 + neg[rest-1])
        }
    }
    println(ans)
}

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

int
main()
{
	char x[1000];
	int i;
	int len;
	int sum;	
	for (;;)
	{
		scanf("%s", x);

		if (strcmp(x, "0") == 0)
			break;

		sum = 0;
		for (i = 0, len = strlen(x); i < len; i++)
		{
			sum += x[i] - '0';
		}
		printf("%d\n", sum);
	}

	return 0;
}

Measured memory_bytes: 536