akhauriyash/Code-Regression huggingface dataset:
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

class Main {

	public static void main(String[] args) {

		FastScanner sc = new FastScanner();
		final long N = sc.nextLong();
		long min = N - 1;

		for (long i = 1; i <= Math.sqrt(N); i++) {
			if (N % i == 0) {

				min = Math.min(min, i + N / i - 2);
			}
		}
		System.out.println(min);

	}

}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
		return hasNextByte();
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
			throw new NumberFormatException();
		return (int) nl;
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}


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

using ll = long long;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define REP(i, n) FOR(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
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;}
const int MOD = 1000000007;

int main() {
    int h, w;
    cin >> h >> w;
    vector<string> s(h + 2);
    string ss;
    s[0] = string(w + 2, '@');
    s[h + 1] = string(w + 2, '@');
    FOR(i, 1, h + 1) {
        cin >> ss;
        s[i] = '@' + ss + '@';
    }

    set<pair<int, int>> r;
    ll total = 0;
    FOR(i, 1, h + 1) {
        FOR(j, 1, w + 1) {
            if (r.count(make_pair(i, j)) == 1) {
                continue;
            }
            deque<pair<int, int>> q;
            q.emplace_back(i, j);
            r.emplace(i, j);
            ll black = 0;
            ll white = 0;
            int a, b;
            while (!q.empty()) {
                tie(a, b) = q.front(); q.pop_front();
                if (s[a][b] == '#') {
                    black++;
                } else {
                    white++;
                }

                if (s[a - 1][b] != '@' && s[a - 1][b] != s[a][b] && r.count(make_pair(a - 1, b)) == 0) {
                    q.emplace_back(a - 1, b);
                    r.emplace(a - 1, b);
                }
                if (s[a + 1][b] != '@' && s[a + 1][b] != s[a][b] && r.count(make_pair(a + 1, b)) == 0) {
                    q.emplace_back(a + 1, b);
                    r.emplace(a + 1, b);
                }
                if (s[a][b - 1] != '@' && s[a][b - 1] != s[a][b] && r.count(make_pair(a, b - 1)) == 0) {
                    q.emplace_back(a, b - 1);
                    r.emplace(a, b - 1);
                }
                if (s[a][b + 1] != '@' && s[a][b + 1] != s[a][b] && r.count(make_pair(a, b + 1)) == 0) {
                    q.emplace_back(a, b + 1);
                    r.emplace(a, b + 1);
                }
            }
            total += black * white;
        }
    }

    cout << total << endl;
}


Measured memory_bytes: 8064
#include <stdio.h>
#include <algorithm>
#include <vector>
 
using namespace std;
 
class p {
public:
	int c, idx;
};
 
bool cmp(const p &i, const p &j) {
	return i.c>j.c;
}
 
p a[51];
int n, k;
 
int main() {
	scanf("%d %d",&n,&k);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i].c);
		a[i].idx=i;
	}
	sort(a+1,a+n+1,cmp);
	vector<int> res;
	for(int i=1;i<=n-1;i++) {
		res.push_back(a[i].idx);
		a[i].c--;
	}
	int cur=a[n].idx;
	bool ok=false;
	while(1) {
		sort(a+1,a+n+1,cmp);
		bool found=false; 
		for(int i=1;i<=n;i++) {
			if(a[i].c) {
				found=true;
				break;
			}
		}
		if(!found) break;
		vector<int> v;
		for(int i=1;i<=n;i++) if(a[i].idx==cur)
			v.push_back(i);
		for(int i=1;i<=n;i++) if(a[i].idx!=cur)
			v.push_back(i);
		for(int i=0;i<v.size();i++) {
			if(a[v[i]].c) {
				a[v[i]].c--;
				res.push_back(a[v[i]].idx);
				if(cur==a[v[i]].idx) {
					if(k==0) ok=true;
					else {
						k--;
						for(int j=1;j<=n;j++) {
							if(v[i]!=j && a[j].c==0) {
								puts("-1");
								return 0;
							}
						}
						if(i==0) {
							cur=a[v.back()].idx;
						} else {
							res.pop_back();
							a[v[i]].c++;
							k++;
							break;
						}
					}
				}
			}
		}
	}
	if(!ok) puts("-1");
	else {
		printf("%d\n",(int)res.size());
		for(int i=0;i<res.size();i++)
			printf("%d ",res[i]);
		puts("");
	}
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD=1e9+7;
ll powmod(ll a, ll k){
    ll ap=a, ans=1;
    while(k){
        if(k&1){
            ans*=ap;
            ans%=MOD;
        }
        ap=ap*ap;
        ap%=MOD;
        k>>=1;
    }
    return ans;
}
ll inv(ll a){
	return powmod(a, MOD-2);
}
ll f[220], invf[220];
void fac(int n){
    f[0]=1;
    for(ll i=1; i<=n; i++) f[i]=f[i-1]*i%MOD;
    invf[n]=inv(f[n]);
    for(ll i=n-1; i>=0; i--) invf[i]=invf[i+1]*(i+1)%MOD;
}
ll comb(int x, int y){
    if(!(0<=y && y<=x)) return 0;
    return f[x]*invf[y]%MOD*invf[x-y]%MOD;
}
int n, m;
vector<P> g[22];
int t[220];
bool used[22];
int d[22];
void dfs(int x){
	used[x]=1;
	for(auto p:g[x]){
		if(p.second>=n-1) continue;
		int y=p.first;
		if(used[y]) continue;
		d[y]=d[x]+1;
		dfs(y);
	}
}
int main()
{
    cin>>n>>m;
	int a[220], b[220];
	for(int i=0; i<m; i++){
		cin>>a[i]>>b[i];
		a[i]--; b[i]--;
		g[a[i]].push_back({b[i], i});
		g[b[i]].push_back({a[i], i});
	}
	for(int i=n-1; i<m; i++){
		d[a[i]]=0;
		fill(used, used+n, 0);
		dfs(a[i]);
		int x=b[i];
		while(x!=a[i]){
			for(auto p:g[x]){
				if(p.second>=n-1) continue;
				if(d[p.first]==d[x]-1){
					x=p.first;
					t[i]^=(1<<p.second);
					break;
				}
			}
		}
	}
	int cnt[1<<19]={};
	for(int i=0; i<(1<<(n-1)); i++){
		for(int j=n-1; j<m; j++){
			if((i&t[j])==t[j]) cnt[i]++;
		}
	}
	fac(m);
	ll invs[220];
	for(ll i=1; i<=m; i++) invs[i]=inv(i);

	ll dp[1<<19]={};
	ll dp2[1<<19]={};
	dp[(1<<(n-1))-1]=1;
	for(int i=(1<<(n-1))-1; i>0; i--){
		int c=popcount(i);
		for(int j=0; j<n-1; j++){
			if(i&(1<<j)){
				ll x=m-c-cnt[i], y=cnt[i]-cnt[i^(1<<j)];
				ll z=comb(x+y, y)*f[y]%MOD;
				(dp[i^(1<<j)]+=z*dp[i])%=MOD;
				(dp2[i^(1<<j)]+=(dp2[i]*invs[x+1]%MOD+dp[i])*(x+y+1)%MOD*z)%=MOD;
			}
		}
	}
  //cout<<dp[0]<<endl;
	cout<<((m+1)*(n-1)*dp[0]-dp2[0]+MOD)%MOD<<endl;
    return 0;
}

Measured memory_bytes: 10496
#include <assert.h>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <algorithm>
#include <numeric>
#include <functional>
#include <iostream>
#include <string>
#include <array>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <bitset>
typedef long long ll;
typedef unsigned long long ull;

#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define DEBUG(vec) for (auto v : vec) { cout << v << " "; } cout << endl;

using namespace std;

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

  ll N;
  cin >> N;

  ll cur = 0;
  REP(i, N + 1) {
    cur += i;
    if (cur >= N) {
      cout << i << endl;
      return 0;
    }
  }
  return 0;
}


Measured memory_bytes: 256
import std.stdio, std.conv, std.array, std.string;
import std.algorithm;
import std.container;
import std.range;
import core.stdc.stdlib;
import std.math;

void main() {
  int ninzu, limit;
  readf("%d %d\n", &ninzu, &limit);
  auto heights = readln.split.to!(int[]);

  auto count = heights.filter!(h => h >= limit).array.length;
  writeln(count);
}


Measured memory_bytes: 4240
import java.util.Scanner;

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

        int n = sc.nextInt();
        int[] s = new int[n + 1];
        for(int i = 0 ; i < n; i++) {
            s[i] = sc.nextInt();
        }
        int q = sc.nextInt();
        int[] t = new int[q];
        for(int i = 0; i < q; i++) {
            t[i] = sc.nextInt();
        }

        int ans = 0;
        for(int i = 0; i < q; i++) {
            s[n] = t[i];
            int j = 0;
            while(s[j] != s[n]) {
                j++;
            }
            if(j != n) ans++;
        }

        System.out.println(ans);

        sc.close();
    }
}


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

int main() {
  string S;
  cin >> S;
  int count = 0;
  if (S.at(2) == S.at(3) && S.at(4) == S.at(5)) {
    cout << "Yes" <<endl;
  }
  else {
    cout << "No" <<endl;
  }
  
}


Measured memory_bytes: 256
import sys
import math
input = sys.stdin.readline

def inlt():
    return(list(map(int,input().split())))
n, d = inlt()
cnt = 0
for i in range(n):
    x, y = inlt()
    if math.sqrt(x**2+y**2)<=d:
        cnt+=1
print(cnt)        

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

using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int main(){
  int A, B; cin >> A >> B;
  if (A <= 8 && B <= 8) cout << "Yay!" << endl;
  else cout << ":(" << endl;

  return 0;
}


Measured memory_bytes: 3596
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>

using namespace std;

#define LOCAL // sumbit source code
#define all(a) begin(a), end(a)
#define printv_(v)            \
    for (auto row : v)        \
    {                         \
        for (auto d : v)      \
        {                     \
            cout << d << " "; \
        }                     \
        cout << endl;         \
    }
#define MOD 1000000007
#define fi first
#define se second
#define PII pair<int, int>
typedef vector<int> VI;
typedef long long ll;

ll quick_pow(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
        {
            res = a * res;
        }
        a = a * a;
        b >>= 1;
    }
    return res;
}

ll gcd(ll a, ll b)
{
    a = abs(a), b = abs(b);
    while (b != 0)
    {
        a %= b;
        swap(a, b);
    }
    return a;
}
// TO-DO

// contest required
#ifdef LOCAL

void solve()
{
    string s, t;
    cin >> s;
    cin >> t;
    if (s == t)
    {
        cout << 0;
        return;
    }
    int dif = 0;
    for (size_t i = 0; i < s.size(); i++)
    {
        if (s[i] != t[i])
        {
            dif++;
        }
    }
    cout << dif;
}

int main()
{
    solve();
    return 0;
}

#endif


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

const int N = 100005;
int n ;

bool cal(vector<int> a) {
    if (n == 1) {
        return 0;
    }
    if (n == 2) {
        return (a[0] + a[1]) & 1;
    }
    int cnt = 0 , sum = 0;
    for (int i = 0 ; i < n ; ++ i) {
        if (a[i] & 1) {
            ++ cnt;
        }
        if (a[i] == 1) cnt = 233;
        sum += a[i] - 1;
        sum &= 1;
    }
    if (cnt > 1) {
        return sum & 1;
    } else {
        vector<int> b(n); int d = 0;
        int f = 0;
        for (int i = 0 ; i < n ; ++ i) {
            if (a[i] & 1) {
                if (a[i] > 1)
                    -- a[i];
                else {
                    f = 1;
                    break;
                }
            }
            d = __gcd(a[i] , d);
        }
        if (f) return sum & 1;
        for (int i = 0 ; i < n ; ++ i) {
            b[i] = a[i] / d;
        }
        return !cal(b);
    }


}

int main() {
    scanf("%d" , &n);
    vector<int> a(n);
    for (int i = 0 ; i < n ; ++ i) {
        scanf("%d" , &a[i]);
    }
    puts(cal(a) ? "First" : "Second");
}


Measured memory_bytes: 19072
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();
// freopen("input.txt", "r", stdin);

int main() {
    int n;
    cin >> n;
    vector<int> arr(n, 0);
    map<int, set<int>> freq;
    freq[0] = {-1};
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
        freq[arr[i]].insert(i);
    }
    vector<ll> ans(n, 0);
    set<int> cur_sm;
    while(true) {
        auto most_it = prev(freq.end());
        if (most_it->first == 0)
            break;
        auto sec_it = prev(prev(freq.end()));
        ll diff = most_it->first - sec_it->first;
        for(int num: most_it->second)
            cur_sm.insert(num);

        ans[*cur_sm.begin()] += diff * cur_sm.size();
        freq.erase(most_it);
    }
    for(int i = 0; i < n; i++)
        cout << ans[i] << endl;
    return 0;
}




Measured memory_bytes: 16256
import java.io.*;
import java.util.StringTokenizer;

public class Main {

    void solve() {
        int N = in.nextInt();
        int result = 0;
        for(int i = 0; i < N; i++) {
            int l = in.nextInt();
            int r = in.nextInt();
            result += (r - l + 1);
        }
        out.println(result);
    }


    FastScanner in;
    PrintWriter out;

    void run() {
        in = new FastScanner();
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }

    public class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastScanner(String s) {
            try {
                br = new BufferedReader(new FileReader(s));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(nextToken());
        }

        public long nextLong() {
            return Long.parseLong(nextToken());
        }

        public double nextDouble() {
            return Double.parseDouble(nextToken());
        }
    }

    public static void main(String[] args) {
        new Main().run();
    }

}

Measured memory_bytes: 19796
#include<cmath>
#include<iostream>
using namespace std;
int main (void){


    int n, d;
    long b, cnt = 0;
    long double a;


    cin >> n >> d;

    for(int i = 0;i < n;i++){
    
        cin >> a >> b;

        a = a * a + b * b;

        a = sqrt(a);

        if(a <= d)
            cnt++;
    }

    cout << cnt << endl;


    return 0;
}

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

int sa(int a,int b){
    if (a>b) return a-b;
    else return b-a; 
}
int main() {
  int N,M;
  cin >> N >> M;
  vector<pair<int,int>> A(N);
  vector<pair<int,int>> C(M);
  for (int i=0; i<N; i++) {
      cin >> A.at(i).first >> A.at(i).second;
  }
  for (int i=0; i<M; i++) {
      cin >> C.at(i).first >> C.at(i).second;
  }
  for (int i=0; i<N; i++) {
      int d=sa(A.at(i).first, C.at(0).first)+sa(A.at(i).second,C.at(0).second);
      int k=1;
      for (int j=0; j<M; j++) {
          if (d>sa(A.at(i).first, C.at(j).first)+sa(A.at(i).second, C.at(j).second)) {
              d=sa(A.at(i).first, C.at(j).first)+sa(A.at(i).second, C.at(j).second);
              k=j+1;
          }
      }
      cout << k << endl;
  }
}

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

const int MAX_N = 1 << 18;
const int M = 300000;
int n,dat[3][2 * MAX_N - 1];

void init(int n_)
{
	n = 1;
	while(n < n_) n *= 2;

	rep(i,2*n-1)
	{
		dat[0][i] = M;
		dat[1][i] = M;
	}
}

void update(int k, int a, int c)
{
	k += n-1;
	dat[c][k] = a;
	while(k > 0)
	{
		k = (k - 1) / 2;
		dat[c][k] = min(dat[c][k*2+1], dat[c][k*2+2]);
	}
}

int query(int a, int b, int k, int l, int r, int c)
{
	if (r <= a || b <= l) return M;

	if (a <= l && r <= b) return dat[c][k];
	else
	{
		int vl = query(a,b,k*2+1,l,(l+r)/2,c);
		int vr = query(a,b,k*2+2,(l+r)/2,r,c);
		return min(vl,vr);
	}
}

int main()
{
	ll Q;
	cin >> n >> Q;
	int initn = n;
	init(n);
	ll ans = (ll(initn)-2) * (ll(initn)-2);
	rep(i,Q)
	{
		int c,x;
		cin >> c >> x;
		x--;
		if (c == 1)
		{
			int t = query(x,n,0,0,n,0);
			if (t == M) t = initn-1;
			//cout << t << endl;
			int vt = query(t,t+1,0,0,n,1);
			update(t,min(vt,x),1);
			ans -= t-1;
		}
		else
		{
			int t = query(x,n,0,0,n,1);
			if (t == M) t = initn-1;
			//cout << t << endl;
			int vt = query(t,t+1,0,0,n,0);
			update(t,min(vt,x),0);
			ans -= t-1;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 7644
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pdi pair<db,int>
#define mp make_pair
#define pb push_back
#define enter putchar('\n')
#define space putchar(' ')
#define eps 1e-8
#define mo 974711
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 + c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
int N,M;
int fa[MAXN],dis[MAXN];
int getfa(int u) {
    if(u == fa[u]) return u;
    else {
	int t = getfa(fa[u]);
	dis[u] += dis[fa[u]];
	return fa[u] = t;
    }
}
void Solve() {
    read(N);read(M);
    for(int i = 1 ; i <= N ; ++i) {
	fa[i] = i;dis[i] = 0;
    }
    int l,r,d;
    for(int i = 1 ; i <= M ; ++i) {
	read(l);read(r);read(d);
	if(getfa(l) == getfa(r)) {
	    if(dis[r] - dis[l] != d) {
		puts("No");
		return;
	    }
	}
	else {
	    int p = getfa(r),q = getfa(l);
	    fa[p] = q;
	    dis[p] = dis[l] - dis[r] + d;
	}
    }
    puts("Yes");
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
    return 0;
}


Measured memory_bytes: 1024
n=gets.to_i
a=$<.read.split.map{|i|i.split ""}
b=a.transpose
r=[]
n.times do |i|
  r<< a[i].count(?.)+(b[i].include?(?#) ? 0:1)
end
if r.min==n+1
  p -1
else
  p r.min+n-b.count{|e|e==[?#]*n}
end

Measured memory_bytes: 18940
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;
 
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)

//最大公約数
long gcd(long a, long b){
	if (a%b==0){
		return b;
	}
	else{
		return gcd(b,a%b);
	}
}

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

typedef long long ll;

int l[100000001];

int main(){
	int x;
	
	cin >> x;
	
	x = abs(x);
	
	int t;
	
	FOR(i,1,x+1){
		l[i] = l[i-1] + i;
		if (l[i] >= x){
			t = i;
			break;
		}
	}
	
	cout << t << endl;
	
	return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	int n, m; cin >> n >> m;
	vi v(n + 1), h(n + 1);
	vi t(m), s(m);
	rep(i, n) cin >> v[i + 1] >> h[i + 1];
	rep(i, m) cin >> t[i] >> s[i];
	
	vi dh(n);
	rep(i, n - 1) dh[i + 1] = dh[i] + abs(h[i + 2] - h[i + 1]);
	rep(i, n) v[i + 1] += v[i];
	rep(i, n) h[i + 1] += h[i];
	
	vector<vi> dp(m + 1, vi(n + 1, -1));
	vector<vi> cost(n + 1, vi(n + 1, -inf));
	
	rep(i, n + 1) for(int j = i; j <= n; j++){
		int x = h[j] - h[i];
		if(i < j) x += dh[j - 1] - dh[i];
		cost[i][j] = x;
	}
	
	vi L(m + 1), R(m + 1, -1);
	R[0] = 0;
	dp[0][0] = 0;
	
	rep(i, m){
		int nL = n + 1, nR = -1;
		dp[i + 1] = dp[i];
		
		for(int j = L[i]; j <= R[i]; j++){
			
			int l = j - 1, r = n, mid;
			if(dp[i][j] + cost[j][n] < s[i]) continue;
			while(l + 1 < r){
				mid = (l + r) / 2;
				if(dp[i][j] + cost[j][mid] < s[i]) l = mid;
				else r = mid;
			}
			nL = min(nL, r);
			nR = max(nR, r);
			
			if(i && dp[i - 1][j] == dp[i][j] && L[i - 1] <= j && j <= R[i - 1]){
				r = R[i] + 1;
			}
			
			for(int k = r; k <= n && v[k] <= t[i]; k++){
				int str = dp[i][j] + cost[j][k];
				nR = max(nR, k);
				
				if(dp[i + 1][k] < str){
					/*
					if(k < check){
						dbg(i, j, k, check, str);
						dbg(dp[i-1]);
						dbg(dp[i]);
						dbg(dp[i+1]);
					}
					assert(k >= check);
					*/
					dp[i + 1][k] = str;
				}
			}
		}
		L[i + 1] = nL; R[i + 1] = nR;
		rep(j, nL) dp[i + 1][j] = -1;
	}
	//rep(i, m + 1) dbg(i, dp[i]);
	
	int ans = -1;
	for(int i = L[m]; i <= R[m]; i++) if(dp[m][i] >= 0){
		ans = i;
		break;
	}
	if(ans < 0) cout << -1 << endl;
	else cout << t[m - 1] - v[ans] << endl;
	return 0;
}


Measured memory_bytes: 50052
import java.util.Scanner;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			double[] a = new double[8];
			for(int i=0;i<8;i++){
				a[i]=cin.nextDouble();
			}
			double dx1=a[2]-a[0];
			double dy1=a[3]-a[1];
			double dx2=a[2+4]-a[0+4];
			double dy2=a[3+4]-a[1+4];
			double n = dx1*dx2+dy1*dy2;
			double EPS=1e-8;
//			System.out.println(n);
			if(0.0<n+EPS&&n-EPS<0.0){
				System.out.println("YES");
			}
			else{
				System.out.println("NO");
			}
			
		}
	}

}

Measured memory_bytes: 23200
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define f(i,a,b) for(ll i=a;i<b;i++)
#define fi(i,a,b) for(ll i=a-1;i>=b;i--)
#define endl '\n'
#define spc " "
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define pi 3.14159265358979323
#define sz(a) (int)((a).size())
#define len(a) (int)(a.length())
#define FOR(i,j,k,l) for(ll i=j;i<k;i+=l)
#define CC(x) cout<<x<<endl


void Fast_IO() {
   ios::sync_with_stdio(0);
   cin.tie(0);
   #ifndef ONLINE_JUDGE
   freopen("input.in","r",stdin);
   freopen("output.out","w",stdout); 
   #endif
} 

int main(){
   //Fast_IO();
   ll n;
   cin>>n;
   ll a[n];
   f(i,0,n) cin>>a[i];
   ll maxi=0,ans=0;
   f(i,0,n){
      if(a[i]<maxi){
         ans+=maxi-a[i];
         a[i]=maxi;
      }
      else maxi=a[i];
   }
   CC(ans);


}





Measured memory_bytes: 5180
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
auto random_address = [] { char *p = new char; delete p; return uint64_t(p); };
const uint64_t SEED = chrono::steady_clock::now().time_since_epoch().count() * (random_address() | 1);
mt19937_64 rng(SEED);
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll dp[1000001],n,k,s[1000001];
const ll mod=998244353;
vector<pll> segs;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=k;i++)
    {
        ll l,r;
        cin>>l>>r;
        segs.push_back({l,r});
    }
    dp[1]=1;
    for(int i=1;i<=n;i++)
    {
        s[i]=(s[i-1]+s[i])%mod;
        dp[i]=(dp[i]+s[i])%mod;
        for(auto j:segs)
        {
            ll l=j.first;
            ll r=j.second;
            ll primul=i+l;
            ll ultimul=i+r;
            if(primul<=n)
                s[primul]=(s[primul]+dp[i])%mod;
            if(ultimul+1<=n)
            {
                s[ultimul+1]=(s[ultimul+1]-dp[i])%mod;
                if(s[ultimul+1]<0)
                    s[ultimul+1]+=mod;
            }
        }
    }
    cout<<dp[n];
    return 0;
}


Measured memory_bytes: 6800
#include <bits/stdc++.h>
using namespace std;
using ll = long long ;
using P = pair<ll, ll>;
using Vec = vector<ll>;
using VecP = vector<P>;
#define REP(i, m, n) for(ll (i) = (m); (i) < (n); ++(i))
#define REPN(i, m, n) for(ll (i) = (m); (i) <= (n); ++(i))
#define REPR(i, m, n) for(ll (i) = (m); (i) >= (n); --(i))
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPR(i, n, 1)
#define co(n) cout << (n) << endl
#define cosp(n) cout << (n) << ' '
#define setp(n) cout << fixed << setprecision(n);
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fs first
#define sc second
template <typename T> bool chmax(T &a, const T& b){if(a < b){a = b; return true;} return false;}
template <typename T> bool chmix(T &a, const T& b){if(a > b){a = b; return true;} return false;}
const ll INF = 1e9+1;
const ll LINF = 1e18+1;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const double PI = acos(-1);
const double EPS = 1e-9;

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

	Vec a(n);
	vector<Vec> t(n, Vec(n, -1));
	rep(i, n){
		cin >> a[i];
		rep(j, a[i]){
			ll x, y;
			cin >> x >> y;
			t[i][x-1] = y;
		}
	}

	Vec honest(n);
	ll ans = 0, cnt = 0;
	rep(i, (1 << n)){
		cnt = 0;
		rep(j, n){
			if(i & (1 << j)){
				honest[j] = 1;
				cnt++;
			}else honest[j] = 0;
		}

		bool flg = true;
		rep(j, n){
			if(i & (1 << j)){
				rep(k, n){
					if(t[j][k] != -1){
						if(t[j][k] != honest[k]){
							flg = false;
							break;
						}
					}
				}
			}
			if(!flg) break;
		}
		if(flg){
			ans = max(ans, cnt);
		}
	}
	co(ans);

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pa pair<int,int>
#define mo 1000000007
#define ll long long
#define se second
#define fi first
using namespace std;
int main(){
	int T;
	scanf("%d",&T);
	while (T--){
		ll a,b;
		scanf("%lld%lld",&a,&b);
		if (a>b) swap(a,b);
		ll x=a*b;
		ll v=max(0,(int)sqrt(x)-2);
		for (;(v+1)*(v+1)<x;v++);
		ll ans=2*v-(a<=v)-(b<=v);
		if (v&&(((x-1)/v==v)||((x-1)/v==b))) ans--;
		//if (v&&d/v==v)
		printf("%lld\n",ans);
	}
}

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

int main(){
  int N, A, B;
  cin >>N >>A >>B;
  
  int sum=0;
  int ans=0;
  int tmp;
  for (int i=1; i<N+1; i++){
    tmp = i;
    sum = 0;
    //cout <<i <<endl;
    for (int j=1; j<6; j++){
      sum += tmp % 10;
      tmp /= 10;
      //cout <<sum <<" " <<N <<endl;
      if (tmp == 0) break;
    }
    if (A<=sum && sum<=B){
      ans += i;
      //cout <<"match!: " <<i <<" " <<sum <<endl;
    }else{
      //cout <<"no match: " <<i <<" " <<sum <<endl;
    }
  }
  cout << ans <<endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
	int a, b;
	cin >> a >> b;
	int sum = 0;
	sum = a + b;
	if (sum % 2 == 1)
	{
		cout << "IMPOSSIBLE" << endl;
	}
	else
	{
		cout << sum / 2 << endl;
	}
	return 0;
}

Measured memory_bytes: 256
s = input()
a = 0
if s[0] == '+':
	a += 1
else:
	a -= 1
if s[1] == '+':
	a += 1
else:
	a -= 1
if s[2] == '+':
	a += 1
else:
	a -= 1
if s[3] == '+':
	a += 1
else:
	a -= 1
print(a)

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

using namespace std;

int main()
{
    int m,n,k;

    cin>>m>>n>>k;

    for(int i=0;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(m*i+n*j-2*i*j==k){
                cout<<"Yes";
                return 0;
            }
        }
    }

    cout<<"No";

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

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

		int a = sc.nextInt();
		int b = sc.nextInt();
		int h = sc.nextInt();
		int m = sc.nextInt();
		
		//0時からの分針の角度を求める
		double Mangle = (m*360.0)/60.0;
		//0時からの時針の角度を求める
		double Hangle = (h*60.0+m)*360.0/(12.0*60.0);
		
		//時針の角度-分針の角度で辺a,bの間の角度を求める
		double MHangle = 0;
		MHangle = Hangle-Mangle;		
		
		//求めた角度からcosを求める
		//(一度ラジアンに変換する必要があるため[角度*(Math.PI/180)]とする)
		double cosA = Math.cos(MHangle*(Math.PI/180.0));
		
		//余弦定理から答えを求める Math.sqrt√(平方根)で求める
		double answer = Math.sqrt((a*a)+(b*b)-(2*a*b*cosA));

		System.out.println(answer);

	}
}

Measured memory_bytes: 35868
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>
#include <numeric>
#include <iomanip>
#include <deque>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <sstream>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

#define rep(i, x) for (int i = 0; i < (int)(x); i++)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()
#define F first
#define S second
#define pb push_back
#define pf push_front

using ll = long long;
using namespace std;
namespace mp = boost::multiprecision;
using cpp_int = mp::cpp_int;
ll M = 1000000007;
typedef pair<int, int> P;

typedef pair<ll, int> pli;
const int MAX = 510000;
const int MOD = 1000000007;
long long modpow(long long a, long long n, long long mod)
{
    long long res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

// a^{-1} mod を計算する
long long modinv(long long a, long long mod)
{
    return modpow(a, mod - 2, mod);
}

/*int main() {
    // 前処理
    COMinit();

    // 計算例
    cout << COM(100000, 50000) << endl;
}*/
cpp_int GCD(cpp_int x, cpp_int y)
{
    return x ? GCD(y % x, x) : y;
}

cpp_int LCM(cpp_int m, cpp_int n)
{
    if ((0 == m) || (0 == n))
        return 0;

    return (m / GCD(m, n) * n); // lcm = m * n / GCD(m,n)
}
int main()
{
    int n;
    cin >> n;
    vector<cpp_int> a(n);
    cpp_int lcm = 1;
    rep(i, n)
    {
        cin >> a[i];
    }
    rep(i, n)
    {
        lcm = LCM(lcm , a[i] ) ;
        //cout << lcm << endl;
    }
    lcm%=M;
    cpp_int ans = 0;
    rep(i, n)
    {
        cpp_int tmp = lcm *modinv((ll)a[i],MOD) % MOD;
        ans += tmp % MOD;
        ans %= M;
        //cout << ans << endl;
    }
    cout << ans % MOD << endl;
}

Measured memory_bytes: 768
N = int(raw_input())
ds = map(int, raw_input().split())
M = int(raw_input())
ts = map(int, raw_input().split())

qs = {}
for d in ds:
  qs[d] = qs.get(d, 0) + 1

ms = {}
for t in ts:
  ms[t] = ms.get(t, 0) + 1

for d, c in ms.iteritems():
  if qs.get(d, 0) < c:
    print "NO"
    exit()

print "YES"

Measured memory_bytes: 50680
#include <iostream>
#include <memory>
#include <memory.h>
#include <cmath>
#include <fstream>
#include <cmath>
#include <numeric>
#include <vector>
#include <stack>
#include <string>
#include <queue>
#include <sstream>
#include <cstdlib>
#include <cassert>
#include <cstdio>
#include <map>
#include <iomanip>
#include <list>
#include <cctype>
#include <algorithm>
#include <complex>
#define USE_MATH_DEFINES
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, m, n) for(int i = m; i < n; i++)
using namespace std;

typedef complex<double> xy_t;
typedef pair<xy_t, xy_t> line;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, P> PP;
typedef pair<int, PP> PPP;
const int INF = 1 << 29;
const double EPS = 1E-10;

bool prime[2000000];
int cnt[2000000];

int main(){
	fill(prime, prime + 2000000, true);
	prime[0] = prime[1] = false;
	for(int i = 2; i * i < 2000000; i++){
		if(prime[i]){
			for(int j = 2 * i; j < 2000000; j += i) prime[j] = false;
		}
	}
	int c = 0;
	rep(i, 2000000){
		if(prime[i])c++;
		cnt[i] = c;
	}

	int n, x, p, m, a, b;
	while(cin >> n && n){
		x = 0;
		rep(i, n){
			cin >> p >> m;
			x--;
			a = max(0, p - m - 1);
			b = min(999983, p + m);
			x += cnt[b] - cnt[a];
		}
		cout << x << endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <string>
#include <cmath>
#include <complex>
#include <numeric>
#include <cassert>

#include <vector>
#include <array>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <utility>

#define PI 3.14159265358979323846
#define int64 long long
#define uint64 unsigned long long
#define coutfix(i) cout << fixed << setprecision(i)		//coutの浮動小数出力の桁数設定
using namespace std;

int main()
{
	string ss;
	cin >> ss;
	cout << ss[0] << (ss.length() - 2) << ss[ss.length() - 1] << endl;
	return 0;
}

Measured memory_bytes: 3608
import java.util.Scanner;

public class Main {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        if(a < b && b < c){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 26136
#include<iostream>
using namespace std;
int main(){
int n;
  cin>>n;
  if(n>=400&&n<=599) cout<<8<<endl;
   if(n>=600&&n<=799) cout<<7<<endl;
   if(n>=800&&n<=999) cout<<6<<endl;
   if(n>=1000&&n<=1199) cout<<5<<endl;
   if(n>=1200&&n<=1399) cout<<4<<endl;
   if(n>=1400&&n<=1599) cout<<3<<endl;
   if(n>=1600&&n<=1799) cout<<2<<endl;
   if(n>=1800&&n<=1999) cout<<1<<endl;
}

Measured memory_bytes: 3624
import itertools

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
a = sorted(a)
b = sorted(b)
c = sorted(c)

ab = []
pivot_a = pivot_b = 0
while pivot_b<n:
    while pivot_a<n and a[pivot_a]<b[pivot_b]:
        pivot_a += 1
    ab.append(pivot_a)
    pivot_b += 1
#print(ab)
ab_sum = list(itertools.accumulate(ab))

bc = []
pivot_a = pivot_b = 0
while pivot_b<n:
    while pivot_a<n and b[pivot_a]<c[pivot_b]:
        pivot_a += 1
    bc.append(pivot_a)
    pivot_b += 1
#print(bc)

res = 0
for i in bc:
    if i!=0:
        res += ab_sum[i-1]
print(res)


Measured memory_bytes: 28532
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define chmax(a, b) a = (a >= b ? a : b)
#define chmin(a, b) a = (a <= b ? a : b)
#define out(a) cout << a << endl
#define outa(a, n) { rep(_, n) cout << a[_] << " "; cout << endl; }
#define outp(a, n) { cout << endl; rep(_, n) cout << a[_].F << " " << a[_].S << endl; }
#define sz(v) (int)v.size()
#define inf (int)(1e9+7)
#define abs(x) (x >= 0 ? x : -(x))
#define ceil(a, b) a / b + !!(a % b)
#define FIX(a) fixed << setprecision(a)
#define LB(v, n) (int)(lower_bound(all(v), n) - v.begin())
#define UB(v, n) (int)(upper_bound(all(v), n) - v.begin())
ll pow(ll a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }


// http://drken1215.hatenablog.com/entry/2019/06/15/114700

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    
    int n;
    cin >> n;
   
    priority_queue<int> first; // 5 4 1
    priority_queue<int, vector<int>, greater<int> > latter; // 6 7 9
    
    ll sum_first = 0, sum_latter = 0;
    ll cons = 0; // 定数項の和
    
    while (n--) {
        int que;
        cin >> que;
        if (que == 2) {
            int x = first.top();
            cout << x << " ";
            out(1LL * sz(first) * x - sum_first + sum_latter - 1LL * sz(latter) * x + cons);
        } else {
            int a, b;
            cin >> a >> b;
            
            cons += b;
            
            // 基本firstに埋めていく方針で
            if (sz(first) > sz(latter)) { // latterに埋める
                
                if (a < first.top()) { // firstからlatterに送ってaはfirstに入れる
                    int tmp = first.top();
                    latter.push(tmp);
                    first.pop();
                    first.push(a);
                    
                    
                    
                    sum_first += a - tmp;
                    sum_latter += tmp;
                } else { // そのままlatterに入れる
                    latter.push(a);
                    
                    sum_latter += a;
                }
            } else { // firstに埋める
                if (sz(first) == 0) { // ないとbad access
                    first.push(a);
                    
                    sum_first += a;
                } else if (a > latter.top()) {
                    int tmp = latter.top();
                    first.push(tmp);
                    latter.pop();
                    latter.push(a);
                    
                    sum_first += tmp;
                    sum_latter += a - tmp;
                } else {
                    first.push(a);
                    
                    sum_first += a;
                }
            }
        }
    }
}


Measured memory_bytes: 3452
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
using namespace std;

template<class T>
void in(vector<T>& V) {
	for (auto itr = V.begin(); itr != V.end(); itr++)cin >> *itr;
	return;
}

template<class T>
void out(vector<T>& V) {
	for (T& itr : V)cout << itr << endl;
	return;
}

vector<vector<long long>> DP;
vector<long long> SUM;
int N, M;
vector<int> S, T;
int MOD = 1e9 + 7;

int main() {
	cin >> N >> M;
	S.resize(N);
	in(S);
	T.resize(M);
	in(T);
	DP.resize(M+1, vector<long long>(N+1,0));
	SUM.resize(N + 1,0);
	for (int t = 1; t <= M; t++) {
		for (int s = 1; s <= N; s++) {
			if (S[s-1] != T[t-1])continue;
			DP[t][s] = SUM[s - 1] + 1;
		}
		for (int s = 2; s <= N; s++) {
			DP[t][s] += DP[t][s - 1];
			DP[t][s] %= MOD;
		}
		for (int s = 1; s <= N; s++) {
			SUM[s] += DP[t][s];
			SUM[s] %= MOD;
		}
	}
	cout << (SUM[N]+1)%MOD << endl;
	return 0;
}

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


class UnionFind {
public:
	vector<int> par;
	vector<int> rank;
	UnionFind(int n) {
		init(n);
	}
	void init(int n) {
		par.resize(n);
		for (int i = 0; i<n; i++) {
			par[i] = i;
		}
		rank.assign(n, 0);
	}
	int find(int x) {
		if (par[x] == x) {
			return x;
		} else {
			return par[x] = find(par[x]);
		}
	}
	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return;

		if (rank[x] < rank[y]) {
			par[x] = y;
		} else {
			par[y] = x;
			if (rank[x] == rank[y]) rank[x]++;
		}
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
};

int main() {
	int H, W;
	cin >> H >> W;

	vector<string> field(H);
	for(int i=0;i<H;i++) {
		cin >> field[i];
	}

	UnionFind uf(H * W);
	for(int i=0;i<H;i++) {
		for(int j=0;j<W;j++) {
			if(i + 1 < H && field[i][j] != field[i + 1][j]) {
				uf.unite(i * W + j, (i + 1) * W + j);
			}
			if (j + 1 < W && field[i][j] != field[i][j + 1]) {
				uf.unite(i * W + j, i * W + j + 1);
			}
		}
	}

	map<int, pair<int, int>> mp;
	for(int i=0;i<H;i++) {
		for(int j=0;j<W;j++) {
			auto& p = mp[uf.find(i * W + j)];
			if(field[i][j] == '#') {
				p.first++;
			}else {
				p.second++;
			}
		}
	}

	ll ans = 0;
	for(auto& p : mp) {
		ans += ll(p.second.first) * p.second.second;
	}
	cout << ans << endl;


	return 0;
}


Measured memory_bytes: 10240
#include<bits/stdc++.h>
using namespace std;
int main()
{
   string s,t;
   cin>>s>>t;
    int ind=-1;
    
   for(int i=0;i<=(int)(s.size()-t.size());i++)
   {
       int c=1;
       for(int j=0;j<t.size();j++)
       {
           if(s[i+j]!='?' && s[i+j]!=t[j])
           {c=0;break;}
       }
       if(c){
           ind=i;}
   }
    if(ind==-1) cout<<"UNRESTORABLE\n";
    else
    {
        int j=0;
        while(j<t.size())
        {
            s[ind+j]=t[j];
            j++;
        }
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='?')
                s[i]='a';
        }
        cout<<s<<"\n";
    }
}

Measured memory_bytes: 256
N = int(input())
A = [int(input()) for _ in range(N)]
nxt = 1 #i=1
cnt = 0
while cnt <= N:
    if A[nxt-1] == 2:
        print(cnt+1)
        exit()
    nxt = A[nxt-1]
    cnt+=1
print(-1)

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

typedef long long ll;

// static const int MAX = 1e6;
// static const int NIL = -1;
// static const ll INF = 1<<21;
// static const ll MOD = 1e9 + 7;

bool compPair(const pair<int, int>& arg1, const pair<int, int>& arg2) {
    return arg1.first > arg2.first;
}

int main(void) {
    string a;
    cin >> a;

    vector<ll> abc(26);
    ll n = a.size();
    for(int i=0;i<n;i++) {
        abc.at(a.at(i)-'a')++;
    }

    ll ans;
    ans = n*(n-1)/2;
    for(int i=0;i<26;i++) {
        ans -= (abc.at(i)*(abc.at(i)-1)/2);
    }
    ans++;

    cout << ans << endl;

    return 0;
}


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

#define int long long

#define pii pair<int, int>

#define x1 x1228
#define y1 y1228

#define left left228
#define right right228

#define pb push_back
#define eb emplace_back

#define mp make_pair                                                                
                                                                                                                                        
#define ff first                                                                  
#define ss second   

#define matr vector<vector<int> > 

#define all(x) x.begin(), x.end()


using namespace std;
typedef long long ll; 
typedef long double ld; 
                                                                                                   
const int maxn = 3e5 + 7, mod = 998244353, inf = 1e18, MAXN = 1e6 + 7;
const double eps = 1e-9;
mt19937 rnd(time(0));
int n; 
int a[maxn]; 
int b[maxn]; 

int id(int x) {
    return (x + n) % n; 
}

bool check(int idd) {
    return b[idd] >= b[id(idd - 1)] + b[id(idd + 1)] + a[idd]; 
}
void solve() { 
    cin >> n;     
    for (int i = 0; i < n; ++i) {
        cin >> a[i]; 
    } 
    for (int i = 0; i < n; ++i) {
        cin >> b[i]; 
    }
    vector<int> can; 
    for (int i = 0; i < n; ++i) {
        if (check(i)) {
            can.pb(i); 
        }
    }
    int ans = 0; 
    while (can.size()) {
        int idd = can.back(); 
        can.pop_back(); 
        int cur = b[id(idd + 1)] + b[id(idd - 1)]; 
        if (check(idd)) {
            int lol = (b[idd] - a[idd]) / cur; 
            ans += lol; 
            b[idd] -= cur * lol; 
        }
        if (check(id(idd - 1))) can.pb(id(idd - 1)); 
        if (check(id(idd + 1))) can.pb(id(idd + 1)); 
    }
    for (int i = 0; i < n; ++i) {
        if (a[i] != b[i]) {
            cout << -1;
            return; 
        } 
    }
    cout << ans; 
}                                
   
signed main() {
#ifdef LOCAL
    freopen("TASK.in", "r", stdin);
    freopen("TASK.out", "w", stdout);
#else 
    
#endif // LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(20); 
    cout << fixed; 
    int t = 1; 
    for (int i = 0; i < t; ++i) {              
        solve();
    }
    return 0;
}  

Measured memory_bytes: 4984
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <tuple>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <numeric>
#include <string.h>
using namespace std;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<29;
const long long  INFL = 1e18;
const int MOD = 1000000007;
const int MAX = 210000;
const int MAX_NUM = 999999999;
string s = "";
string f_str = "";
string b_str = "";
void solve() {
    cin >> s;
    f_str = s.substr(0, 2);
    b_str = s.substr(2, 2);
    if (f_str.compare("12") > 0) {
        if(b_str.compare("00") == 0) {
            cout << "NA" << endl;
        } else if(b_str.compare("12") > 0) {
            cout << "NA" << endl;
        } else {
            cout << "YYMM" << endl;
        }
    } else if (f_str.compare("00") > 0) {    //01 ~ 11
        if(b_str.compare("00") == 0) {
            cout << "MMYY" << endl;
        } else if(b_str.compare("12") > 0) {
            cout << "MMYY" << endl;
        } else {
            cout << "AMBIGUOUS" << endl;
        }
    } else {    //00
        if (b_str.compare("00") == 0) {
            cout << "NA" << endl;
        } else if (b_str.compare("12") > 0) {
            cout << "NA" << endl;
        } else {
            cout << "YYMM" << endl;
        }
    }
    return;
}
//逆元を求める関数
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++) {
      fac[i] = fac[i-1] * i % MOD;
      inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
      finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
//組み合わせ
long long COM (int n, int k) {
    if(n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}
int main(int args, char* argv[]) {
    solve();
}

Measured memory_bytes: 256