akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string>
using namespace std;

class dice {
public:
	int a[6];
	int b;
	void moveN() {
		b = a[0];
		a[0] = a[1];
		a[1] = a[5];
		a[5] = a[4];
		a[4] = b;
	}

	void moveS() {
		b = a[0];
		a[0] = a[4];
		a[4] = a[5];
		a[5] = a[1];
		a[1] = b;
	}

	void moveE() {
		b = a[0];
		a[0] = a[3];
		a[3] = a[5];
		a[5] = a[2];
		a[2] = b;
	}

	void moveW() {
		b = a[0];
		a[0] = a[2];
		a[2] = a[5];
		a[5] = a[3];
		a[3] = b;
	}

	void moveR() {
		b = a[1];
		a[1] = a[2];
		a[2] = a[4];
		a[4] = a[3];
		a[3] = b;
	}

	void moveL() {
		b = a[1];
		a[1] = a[3];
		a[3] = a[4];
		a[4] = a[2];
		a[2] = b;
	}
};

int main() {
	dice dice1, dice2;
	for (int i = 0; i < 6; i++) {
		cin >> dice1.a[i];
	}

	for (int i = 0; i < 6; i++) {
		cin >> dice2.a[i];
	}

	if (dice1.a[2] == dice2.a[2] && dice1.a[3] == dice2.a[3] && dice1.a[4] == dice2.a[4] && dice1.a[0] == dice2.a[0] && dice1.a[1] == dice2.a[1] && dice1.a[5] == dice2.a[5]) {
		cout << "Yes" << endl;
		return 0;
	}

	for (int i = 0; i < 4; i++) {
		dice2.moveR();
		for (int j = 0; j < 4; j++) {
			dice2.moveN();
			if (dice1.a[2] == dice2.a[2] && dice1.a[3] == dice2.a[3] && dice1.a[4] == dice2.a[4] && dice1.a[0] == dice2.a[0] && dice1.a[1] == dice2.a[1] && dice1.a[5] == dice2.a[5]) {
				cout << "Yes" << endl;
				return 0;
			}
		}
	}

	for (int i = 0; i < 4; i++) {
		dice2.moveE();
		for (int j = 0; j < 4; j++) {
			dice2.moveN();
			if (dice1.a[2] == dice2.a[2] && dice1.a[3] == dice2.a[3] && dice1.a[4] == dice2.a[4] && dice1.a[0] == dice2.a[0] && dice1.a[1] == dice2.a[1] && dice1.a[5] == dice2.a[5]) {
				cout << "Yes" << endl;
				return 0;
			}
		}
	}

	cout << "No" << endl;

	return 0;
}


Measured memory_bytes: 3128
fn main() {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();
    let n: usize = iter.next().unwrap().parse().unwrap();
    let m: usize = iter.next().unwrap().parse().unwrap();

    println!("{}", if n==m { "Yes" } else {"No"});
}


Measured memory_bytes: 4352
#include <cctype>
#include <cstdio>
#include <vector>
#include <algorithm>

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

using namespace std;

const int INF=1<<29;

int h,w;
char B[50][51];

struct point{ int x,y; };
vector<point> pos[128];

int dp[50][50][50][50];
int dfs(int t,int l,int b,int r){
	if(h<=t || w<=l || b<0 || r<0
	|| B[t][l]=='#' || B[b][r]=='#') return -INF;

	if(t== b  && l== r
	|| t== b  && l==r+1
	|| t==b+1 && l== r ) return 0;

	if(t>b || l>r) return -INF;

	if(dp[t][l][b][r]!=-1) return dp[t][l][b][r];

	int res=-INF;
	res=max(res,dfs(t+1,l,b,r));
	res=max(res,dfs(t,l+1,b,r));
	res=max(res,dfs(t,l,b-1,r));
	res=max(res,dfs(t,l,b,r-1));
	if(islower(B[t][l]) && toupper(B[t][l])==B[b][r]){
		res=max(res,dfs(t+1,l,b-1,r)+1);
		res=max(res,dfs(t+1,l,b,r-1)+1);
		res=max(res,dfs(t,l+1,b-1,r)+1);
		res=max(res,dfs(t,l+1,b,r-1)+1);
	}

	if(islower(B[t][l])){
		char c=B[t][l]-'a'+'A';
		rep(k,pos[c].size()){
			int x=pos[c][k].x,y=pos[c][k].y;
			if(t<=y && y<=b && l<=x && x<=r && !(y==b && x==r)){
				res=max(res,dfs(t,l,y,x)+dfs(y,x,b,r));
			}
		}
	}

	return dp[t][l][b][r]=res;
}

int main(){
	for(;scanf("%d%d",&h,&w),h;){
		rep(i,h) scanf("%s",B[i]);

		rep(c,128) pos[c].clear();
		rep(i,h) rep(j,w) pos[B[i][j]].push_back((point){j,i});

		rep(t,h) rep(l,w) rep(b,h) rep(r,w) dp[t][l][b][r]=-1;
		printf("%d\n",max(dfs(0,0,h-1,w-1),-1));
	}

	return 0;
}

Measured memory_bytes: 25596
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
typedef pair<int, P> E;
const LL MOD = 1000000007LL;
LL f(LL b, LL n) {
	LL ret = 0;
	while (n > 0) {
		ret += n%b;
		n /= b;
	}
	return ret;
}
int main() {
	LL n, s;
	cin >> n >> s;
	if (n == s) {
		cout << n + 1 << endl;
		return 0;
	}
	for (LL i = 2; i*i <= n; i++) {
		if (f(i, n) == s) {
			cout << i << endl;
			return 0;
		}
	}
	if (n < s) {
		cout << -1 << endl;
		return 0;
	}
	LL ans = 1LL << 60;
	for (LL i = 1; i*i <= n - s; i++) {
		if ((n - s) % i) continue;
		LL b = (n - s) / i + 1;
		if (f(b, n) == s) ans = min(ans, b);
	}
	if (ans == 1LL << 60) {
		cout << -1 << endl;
		return 0;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
#define F(i,a,n) for(int i=a;i<n;i++)
#define mod 1000000007 
#define pb push_back
int main(){
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
	int w=1;
	// cin>>w;
	while(w--){
		long long n;
		cin>>n;
		ll ans=1;
		F(i,0,n){
			ans=(ans*10)%mod;
		}
		ll x=1,y=1;
		F(i,0,n){
			x=(x*9)%mod;
			y=(y*8)%mod;
		}
		x=(2*x)%mod;

		ans=(ans-x+mod+y)%mod;
		cout<<ans;
	}
	return 0;
}

Measured memory_bytes: 3588
using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
namespace Atcoder_0404
{
    class Program
    {
        static void Main(string[] args)
        {
            var k = GetInput_int()[0];
            var s = GetInput_string()[0];
            if (s.Length <= k)
            {
                Console.WriteLine(s);
            }
            else
            {
                var result = s.Substring(0, k)+"...";
                Console.WriteLine(result);
            }
        }
        
        #region input
        

        static string[] GetInput_string()
        {
            var input = Console.ReadLine().Split(' ');
            return input;
        }

        static int[] GetInput_int()
        {
            var input = GetInput_string();
            var result = new int[input.Length];
            for (int i = 0; i < result.Length; i++)
            {
                result[i] = int.Parse(input[i]);
            }
            return result;
        }
        static long[] GetInput_long()
        {
            var input = GetInput_string();
            var result = new long[input.Length];
            for (int i = 0; i < result.Length; i++)
            {
                result[i] = long.Parse(input[i]);
            }
            return result;
        }
        #endregion
        #region sonota
        static void Swap_array<T>(T[] target, int a, int b)
        {
            T temp = target[a];
            target[a] = target[b];
            target[b] = temp;
        }
        static void Swap_list<T>(List<T> target, int a, int b)
        {
            T temp = target[a];
            target[a] = target[b];
            target[b] = temp;
        }
        /// <summary>
        /// 最大公約数
        /// </summary>
        public static int GCD(int a, int b)
        {

            /* 自然数 a > b を確認・入替 */
            if (a < b)
            {
                int tmp = a;
                a = b;
                b = tmp;
            }

            /* ユークリッドの互除法 */
            int r = a % b;
            while (r != 0)
            {
                a = b;
                b = r;
                r = a % b;
            }
            return b;
        }

        /// <summary>
        /// 最小公倍数
        /// </summary>
        public static int LCM(int a, int b)
        {
            int x = a * b;
            b = GCD(a, b);
            return x / b;

        }
        #endregion

        static long mod = 1000000000 + 7;
    }

}

Measured memory_bytes: 27496
N, K = map(int, input().split())
P = tuple(map(int, input().split()))

PMAX = 1000
s = [0] * (PMAX + 1)
for i in range(PMAX):
    s[i+1] = s[i] + (i + 1)

e = [0] * (N + 1)
for i, p in enumerate(P):
    e[i+1] = e[i] + (s[p] / p)

ans = 0
for i in range(N - K + 1):
    ans = max(ans, e[i+K] - e[i])
print(ans)

Measured memory_bytes: 32116
package main

import (
	"fmt"
	"strconv"
	"strings"
)

func main(){
	var money int
	var n int
	fmt.Scan(&money, &n)
	list := make([]string, n)
	for i, _ := range list {
		fmt.Scan(&list[i])
	}

	for i := money; i < 10 * money; i++{
		isMoney := true
		for _, s := range list {
			if strings.Contains(strconv.Itoa(i), s){
				isMoney = false
				break
			}
		}
		if isMoney {
			fmt.Print(i)
			return
		}
	}

}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
#define ll  long long int
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);srand(time(NULL));
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
const int N = 100005;
int main()
{
  
   FAST;
   ll n;
   cin >> n;
   ll a[n];
   ll sum = 0;
   for(ll i=0;i<n;i++)
   {
       cin >> a[i];
   }
   ll ans = 0;
   ll temp =1;
   for(ll i=0;i<62;i++)
   {
       ll cnt = 0;
       for(ll j=0;j<n;j++)
       {
           if(temp & a[j])  cnt++;
       }
       ll d = temp;
       d %= MOD;
       d *= cnt;
       d %= MOD;
       d *= (n-cnt);
       d %= MOD;
       ans = (ans + d)%MOD;
       temp *= 2;
   }
   cout<<ans;
}

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

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

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

	int n;
	cin >> n;

	string board[n];
	rep(i, n) cin >> board[i];

	int ans = 0;

	// (a, b)での平行移動が良い盤面　⇔　(a+1, b+1)での平行移動が良い盤面
	// なので、(0, 0), (0, 1), ...,  (0, n-1) だけチェックすればよい
	rep(b, n){
		char board2[n][n];
		rep(i, n) rep(j, n) board2[i][j] = board[i][(j + b) % n];

		bool ok = true;
		rep(i, n){
			rep(j, n){
				if(board2[i][j] != board2[j][i]){
					ok = false;
					break;
				}
			}
			if(!ok) break;
		}
		if(ok) ans += n;
	}
	
	cout << ans << endl;
}

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

int main() {
    int n, five = 0, seven = 0;
  	rep(i, 3){
      	cin >> n;
    	if(n == 5){
          	five++;
        }else if(n == 7){
        	seven++;
        }
    }
  	if(five == 2 && seven == 1){
    	cout << "YES" << endl;
    }else{
    	cout << "NO" << endl;
    }
    return 0;
}

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

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;

#define REP(i, x, n) for(ll i=x; i<(ll)n; ++i)
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()

ll comb(ll n, ll m){
    static vvll d(2001, vll(2001, 0));
    if(n==m||n==0||m==0) return 1;
    if(d[n][m]>0) return d[n][m];
    if(n<m) return 0;
    ll a = comb(n-1, m-1);
    ll b = comb(n-1, m);
    ll res = (a+b) % 1000000007;
    d[n][m] = res;
    return res;
}

int main(){
    ll N, K;
    cin >> N >> K;
    REP(i, 1, K+1){
        ll a = (comb(N-K+1, i) * comb(K-1, i-1)) % 1000000007;
        cout << a << endl;
    }
}


Measured memory_bytes: 31744
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <map>
using namespace std;


int main (int argc, char const *argv[])
{
    int N;
    cin>>N;
    if (N==1) {
        cout<<"Hello World"<<endl;
    }else
    {
        int A,B;
        cin>>A>>B;
        cout<<A+B<<endl;
    }
    
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
//#define int long long
 
const int N = 1e5 + 5;


int main()
{
   IOS;
   int n,div=0, pay=0, ch=0;
   cin >> n;

   cout << (1000-n%1000)%1000 << endl;


   


   return 0;
}
 

Measured memory_bytes: 3600
import java.util.Scanner;
class Main
 {
   public static void main(String[] args)
      {
      Scanner stdIn = new Scanner(System.in);
      int a = stdIn.nextInt();
      int b = stdIn.nextInt();
      int a1 = a*b;
      int a2 = 2*(a+b);
      System.out.printf("%d %d\n", a1, a2);
      }
 }



Measured memory_bytes: 26152
#include <iostream>
#include <cmath>

using namespace std;

int main() {
  int n;
  cin >> n;
  int a = ceil((double)n / 1.08);
  if (floor(a * 1.08) == n) {
    cout << a << endl;
  } else {
    cout << ":(" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
#define FastIO ios::sync_with_stdio(false), cin.tie(NULL);
#define all(x) x.begin(), x.end()
#define pb push_back
#define endl '\n'
typedef long long ll;


int main()
{
	FastIO;
	int n, k;
	cin >> n >> k;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int temp;
		cin >> temp;
		if (temp >= k) ans++;
	}
	cout << ans;
}


Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    vector< int > l(m), r(m), d(m);
    queue< int > que;
    vector< bool > used(m, false);
    int F;
    vector< vector< int > > vec(n, vector< int >(0));
    for (int i = 0; i < m; i++) {
        cin >> l[i] >> r[i] >> d[i];
        l[i]--;
        r[i]--;
        vec[l[i]].push_back(i);
        vec[r[i]].push_back(i);
    }
    vector< int > x(n, INT_MIN);

    bool checked = false;
    while (!checked) {
        int G;
        for (int i = 0; i < m; i++) {
            if (!used[i]) {
                checked = true;
                G = l[i];
                que.push(i);
                used[i] = true;
                break;
            }
        }
        if (checked) {
            for (int i = 0; i < m; i++) {
                if (!used[i] && (l[i] == G || r[i] == G)) {
                    que.push(i);
                    used[i] = true;
                }
            }
        } else {
            break;
        }
        x[G] = 0;
        while (que.size()) {
            int j = que.front();
            que.pop();

            if (x[r[j]] == INT_MIN && x[l[j]] != INT_MIN) { //lが分かっていてrが不明な状況
                x[r[j]] = x[l[j]] + d[j];
                for (int i = 0; i < vec[r[j]].size(); i++) {
                    int q = vec[r[j]][i];
                    if (!used[q]) {
                        que.push(q);
                        used[q] = true;
                    }
                }
            } else if (x[l[j]] == INT_MIN && x[r[j]] != INT_MIN) { //rが分かっていてlが不明な状況
                x[l[j]] = x[r[j]] - d[j];
                for (int i = 0; i < vec[l[j]].size(); i++) {
                    int q = vec[l[j]][i];
                    if (!used[q]) {
                        que.push(q);
                        used[q] = true;
                    }
                }
            } else if (x[l[j]] != INT_MIN && x[r[j]] != INT_MIN) { //どちらも分かっている状況 -> 答えあわせをして間違っていたら"No"
                if (x[r[j]] - x[l[j]] != d[j]) {
                    cout << "No" << endl;
                    return 0;
                }
            } else { //この分岐には入るはずがない
                cout << "Error!" << endl;
            }
        }

        checked = true;
        for (int i = 0; i < m; i++) {
            if (!used[i])
                checked = false;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 9856
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(),v.end()
#define pb push_back
template<class T>void chmax(T &a,T b){if(a<b)a=b;}
template<class T>void chmin(T &a,T b){if(a>b)a=b;}
constexpr int INF=1000000000000000000;
constexpr int mod=1000000007;
constexpr double eps=1e-8;
constexpr double pi=3.14159265358979323846264338;
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}
bool prime(int a){
    if(a==1)return false;
    for(int i=2;i*i<=a;i++){
        if(a%i==0)return false;
    }
    return true;
}
int modpow(int a,int b){
    if(b==0)return 1;
    if(b%2)return modpow(a,b-1)*a%mod;
    int memo=modpow(a,b/2);
    return memo*memo%mod;
}
vector<int>kaijo,invkaijo;
void init_fact(int n){
    kaijo.resize(n+1);
    invkaijo.resize(n+1);
    kaijo[0]=1;
    for(int i=1;i<=n;i++){
        kaijo[i]=kaijo[i-1]*i;
        kaijo[i]%=mod;
    }
    rep(i,n+1)invkaijo[i]=modpow(kaijo[i],mod-2);
}
int comb(int a,int b){
    if(a<b)return 0;
    if(a<0||b<0)return 0;
    return kaijo[a]*modpow(kaijo[a-b],mod-2)%mod*modpow(kaijo[b],mod-2)%mod;
}
int inv(int x){
    x=modpow(x,mod-2);
    return x;
}

signed main(){
    cin.tie(0);ios::sync_with_stdio(false);
    int k;
    string s;
    cin>>k>>s;
    if(s.size()<=k)cout<<s<<endl;
    else{
        cout<<s.substr(0,k)<<"..."<<endl;
    }
    return 0;
}

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

int main() {
    ll N,A,B;
    cin >> N >> A >>B;
    if((N+A-1)/A > B || B>(N-A)+1){
        cout << -1 << endl;
        return 0;
    }
    ll loop = 0;
    while(N>0){
        ll maxB = loop + N;
        if(maxB < B +A){
            ll exceeded = maxB-B;
            for(int i=0;i <exceeded+1;i++){
                cout << N- exceeded +i << " ";
            }
            loop++;
            for(int i=0;i<B-loop;i++){
                cout << B-loop-i <<" ";
            }
            break;
        }
        for(int i=0;i<A;i++){
            cout << N-A +i+1 <<" ";
        }
        N-=A;
        loop++;
        
    }
    cout << endl;

    return 0;
}

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

typedef long long LL;
const int M=16;
int a[M][M];

LL sum[(1<<M)+5];
LL dp[(1<<M)+5];

int main()
{
	int n; scanf("%d",&n);
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			scanf("%d",&a[i][j]);
	int mask=1<<n;
	for(int i=1;i<mask;i++)
	{
		int j=0;
		for(;j<n;j++)
			if(i&(1<<j)) break;
		sum[i]=sum[i^(1<<j)];
		for(int k=j+1;k<n;k++)
			if(i&(1<<k)) sum[i]+=a[j][k];
	}
	for(int i=1;i<mask;i++)
	{
		for(int j=i;j!=0;j=(j-1)&i)
			dp[i]=max(dp[i],sum[j]+dp[i^j]);
	}
	printf("%lld\n",dp[mask-1]);
	return 0;
}

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

string A[51];
int T[51];
int main() {
 int ans = 0;
  int n;
  cin >> n;
  for(int i=0; i<n; i++) {
    cin >> A[i] >> T[i];
  }
  string x;
  cin >> x;
  int i;
  for(i=0; i<n; i++) {
    if(x == A[i]) break;
  }
  for(i=i+1; i<n; i++) {
    ans += T[i];
  }
    
  
  cout << ans << endl;
 return 0; 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
using namespace std;
const ll maxn = 1e6 + 7;
const ll mod = 1e9 + 7;
ll q, t, n, m, k, ans, a[maxn], b[maxn];
priority_queue<ll> pr;
string s, ss[maxn], str;
map<ll, ll> mp;
void sol()
{
    cin >> s;
    n = s.length();
    s = " " + s;
    ans = 0;
    t = 1;
    m = 0;
    mp[0] = 1;
    for(int i = n; i > 0; i --)
    {
        m += (s[i] - '0') * t;
        m %= 2019;
        ++mp[m];
        t *= 10;
        t %= 2019;
    }
    ans = 0;
    for(auto u : mp)
        ans += u.second * (u.second - 1) / 2;
    cout << ans;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    sol();
}


Measured memory_bytes: 34952
#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,NAME,...) NAME
#define pr(...) GET_MACRO(__VA_ARGS__,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__)
#define pr1(a) (#a)<<"="<<(a)
#define pr2(a,b) pr1(a)<<", "<<pr1(b)
#define pr3(a,b,c) pr2(a,b)<<", "<<pr1(c)
#define pr4(a,b,c,d) pr3(a,b,c)<<", "<<pr1(d)
#define pr5(a,b,c,d,e) pr4(a,b,c,d)<<", "<<pr1(e)
#define int long long
#define double long double
using namespace std;
const int N = 100010;
const int INF = 1LL<<55;
const int mod = (1e9)+7;
const double EPS = 1e-8;
const double PI = 6.0 * asin(0.5);
typedef pair<int,int> P;
typedef long long ll;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
ostream& operator<<(ostream& o,P p){return o<<"("<<p.first<<","<<p.second<<")";}
istream& operator>>(istream& i,P &p){return i>>p.first>>p.second;}
ostream& operator<<(ostream& o,vector<auto> &a){int i=0;for(auto t:a)o<<(i++?" ":"")<<t;return o;}
istream& operator>>(istream& i,vector<auto> &a){for(auto &t:a)i>>t;return i;}
void prArr(auto a,string s=" "){int i=0;for(auto t:a)cout<<(i++?s:"")<<t;cout<<endl;}


signed main(){
  int n,A,B,C,D;
  cin>>n>>A>>B>>C>>D;

  int a = ((n-1) / A + 1) * B;
  int b = ((n-1) / C + 1) * D;
  int ans = min(a,b);
  cout<<ans<<endl;
  
  return 0;
}



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

using namespace std;


int main()
{
	char b;
	cin>>b;
	if((int)b>=65 && (int)b<=90)
	{
		cout<<"A"<<endl;
	}
	else
	{
		cout<<"a"<<endl;
	}
	return 0;
}

Measured memory_bytes: 3592
using System;
using System.IO;
using System.Linq;

namespace AGC040
{
    class A
    {
        static void Main(string[] args)
        {
            //StreamReader sr = new StreamReader(@"test");
            //string S = sr.ReadLine();
            string S = Console.ReadLine();
            long[] res = new long[S.Length + 1];
            long index = 1;
            for (int i = 0; i < S.Length; i++)
            {
                if (S[i] == '<') { res[i + 1] = index; index++; }
                else { index = 1; }
            }

            index = 1;
            for (int i = S.Length - 1; i >= 0; i--)
            {
                if (S[i] == '>') { res[i] = Math.Max(res[i], index); index++; }
                else { index = 1; }
            }

            long sum = 0;
            for (long i = 0; i < S.Length + 1; i++)
            {
                sum += res[i];
            }

            Console.WriteLine(sum);

        }
    }
}


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

#define mp make_pair
#define X first
#define Y second
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FOD(i, a, b) for(int i = a; i >= b; i--)

using namespace std;

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

const int N = 3e5 + 10;
const int M = 1e5 + 10;

struct _BIT{
    int d[M];
    void update(int x, int val){
        for(; x < M; x += x & -x)
            d[x] += val;
    }
    int get(int x){
        int res = 0;
        for(; x > 0; x -= x & -x)
            res += d[x];
        return res;
    }
} bit;

int n, m;
ii a[N];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    FOR(i, 1, n)
        cin >> a[i].X >> a[i].Y;
    sort(a + 1, a + 1 + n, [](const ii &a, const ii &b){
            return (a.Y - a.X) < (b.Y - b.X);
         });
    int p = 0;
    FOR(d, 1, m){
        while (p < n && (a[p + 1].Y - a[p + 1].X) < d){
            p++;
            bit.update(a[p].X, 1);
            bit.update(a[p].Y + 1, -1);
        }
        int cnt = n - p;
        for(int x = d; x <= m; x += d)
            cnt += bit.get(x);
        cout << cnt << endl;
    }
    return 0;
}

Measured memory_bytes: 3712
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;


int main() {
	string s;
	int K;

	cin >> s >> K;
	int ssize = s.size();

	set<string> strset;
	for(int i = 1; i <= K; i++) {
		for(int j = 0; j <= ssize - i; j++) {
			string sub = s.substr(j, i);
			//cout << sub << endl;
			strset.insert(sub);
		}
	}
	
	auto itr = strset.begin();
	for(int i = 0; i < K - 1; i++) {
		++itr;
	}
	cout << *itr << endl;

	return 0;
}


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

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

  int d;
  cin >> d;

  if (d == 25) {
    cout << "Christmas" << endl;
  } else if (d == 24) {
    cout << "Christmas Eve" << endl;
  } else if (d == 23) {
    cout << "Christmas Eve Eve" << endl;
  } else {
    cout << "Christmas Eve Eve Eve" << endl;
  }

}


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

#define fast_io ios_base::sync_with_stdio(false) ; cin.tie(0); cout.tie(0);

int main() {
    fast_io;
    
    vector<int> arr;

    string s;
    cin>>s;

    for(int i=0;i<s.length();i++) {
        arr.push_back(s[i]-'0');
    }

    int total=0;
    for(int i=0;i<s.length();i++) {
        total+=arr[i];
    }

    if(total%9==0) {
        cout<<"Yes"<<endl;
    }
    else {
        cout<<"No"<<endl;
    }

}




Measured memory_bytes: 4364
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
typedef long long ll;
using namespace std;

int lcs(string x,string y){
  int xl=x.length(),yl=y.length();
  int dp[1001][1001],i,j;

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

  for(i=1;i<=xl;i++){
    for(j=1;j<=yl;j++){
      if(x[i-1]==y[j-1]){
        dp[i][j]=dp[i-1][j-1]+1;
      }
      else{
        dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
      }
    }
  }

  return dp[xl][yl];
}

int main(void){
  int q,i;
  string x,y;
  
  cin>>q;
  for(i=0;i<q;i++){
    cin>>x>>y;
    cout<<lcs(x,y)<<endl;
  }

  return 0;
}


Measured memory_bytes: 7104
#include<stdio.h>
char c[100][100];
int main(){
	int a;
	int b;
	while(scanf("%d%d",&a,&b),a){
		for(int i=0;i<a;i++)
			for(int j=0;j<b;j++)
				scanf(" %c",&c[i][j]);
		
		int s=0;
		int t=0;
		while(1){
			switch(c[s][t]){
				case '>':
					c[s][t]='x';
					t++;
					break;
				case '<':
					c[s][t]='x';
					t--;
					break;
				case 'v':
					c[s][t]='x';
					s++;
					break;
				case '^':
					c[s][t]='x';
					s--;
					break;
			}
			if(c[s][t]=='x')break;
			if(c[s][t]=='.')break;
		}
		if(c[s][t]=='x')printf("LOOP\n");
		else printf("%d %d\n",t,s);
	}
}

Measured memory_bytes: 0
class Dice():
    def __init__(self, dice_labels):
        self.top = dice_labels[0]
        self.south = dice_labels[1]
        self.east = dice_labels[2]
        self.west = dice_labels[3]
        self.north = dice_labels[4]
        self.bottom = dice_labels[5]

    def roll(self, str_direction):
        if str_direction == 'E':
            self.__rot_to_east()
        elif str_direction == 'W':
            self.__rot_to_west()
        elif str_direction == 'S':
            self.__rot_to_south()
        elif str_direction == 'N':
            self.__rot_to_north()

    def __rot_to_east(self):
        self.top, self.east, self.west, self.bottom = (self.west, self.top, self.bottom, self.east)

    def __rot_to_west(self):
        self.top, self.east, self.west, self.bottom = (self.east, self.bottom, self.top, self.west)

    def __rot_to_south(self):
        self.top, self.south, self.north, self.bottom = (self.north, self.top, self.bottom, self.south)

    def __rot_to_north(self):
        self.top, self.south, self.north, self.bottom = (self.south, self.bottom, self.top, self.north)

dice_labels = input().split(' ')
rot_operations = list(input())
dice = Dice(dice_labels)

for roll_direction in rot_operations:
    dice.roll(roll_direction)

print(dice.top)



Measured memory_bytes: 5572
#include <stdio.h>
#define N 1000000
int binarysearch(int*,int,int);
int main(){
  int i,n,S[N],q,t,sum=0;
  
  scanf("%d",&n);
  for(i=0;i<n;i++)
    scanf("%d",&S[i]);

  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&t);
    if(binarysearch(S,n,t))sum++;
  }

  printf("%d\n",sum);

  return 0;
}
int binarysearch(int*S,int n,int t){
  int left=0,right=n,mid;
  while(left<right){
    mid=(left+right)/2;
    if(t==S[mid])return 1;
    else if(t<S[mid])right=mid;
    else left=mid+1;
  }
  return 0;
}



Measured memory_bytes: 2128
import sys
from collections import Counter
n = int(input())
x_ls = [int(i) for i in sys.stdin.readline().split()]
ct = Counter(x_ls)
INF = 10**18
ans = INF
for i in range(1,101,1):
    res = 0
    for k, v in ct.items():
        res += v * abs(k - i) ** 2
    ans = min(res, ans)
print(ans)

Measured memory_bytes: 3572
#include<iostream>

int main(void){
  int N;
  std::string S;
  std::cin >> N;
  std::cin >> S;
  int sum=1;
  for(int i=1;i<N;i++){
    if(S[i]!=S[i-1])sum++;
  }
  std::cout << sum;
  return 0;
}


Measured memory_bytes: 512
#include<stdio.h>
#include<string.h>
 
int main(){
char s[16];
  int i,x=0;
  scanf("%s",&s);
  for(i=0;i<15;i++){
   if(s[i]=='\0')break;
   else if(s[i]=='x')x++;
  }
  if(x<8)printf("YES\n");
  else printf("NO\n");
  return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
int main()
{
    char a[4][4];
    char b[4][4];
    int sum=0;
    for(int i=0; i<2; i++)
    {
        scanf("%s",&a[i]);
    }
    if(a[0][0]==a[1][2])
        sum++;
    if(a[0][1]==a[1][1])
        sum++;
    if(a[0][2]==a[1][0])
        sum++;
    if(sum==3)
    {
        printf("YES\n");
    }
    else
    {
        printf("NO\n");
    }
    return 0;
}


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

import math

n=int(input())
p=list(map(int,input().split()))
q=list(map(int,input().split()))

d1=[i+1 for i in range(n)]
d2=[i+1 for i in range(n)]
mp=[math.factorial(i) for i in reversed(range(n))]

np=0
nq=0
for i in range(n):
    np+=d1.index(p[i])*mp[i]
    d1.remove(p[i])
    nq+=d2.index(q[i])*mp[i]
    d2.remove(q[i])
print(abs(np-nq))



Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define rep(i,n) for(ll i=0;i<n;i++)
#define inf 999999999
const int mod = 1000000007;
ll cnt = 0;
int dp[10010][10010];

int main(){
    int n,W;    cin >> n >> W;
    int v[n],w[n];
    for(int i=0;i<n;i++){
        cin >> v[i] >> w[i];
    }

    for(int i=n-1;0<=i;i--){
        for(int j=0;j<=W;j++){
            if(j<w[i]){
                dp[i][j] = dp[i+1][j];
            }else{
                dp[i][j] = max(dp[i+1][j] , dp[i+1][j-w[i]]+v[i]);
            }
        }
    }

    cout << dp[0][W] << endl;
}



Measured memory_bytes: 7000
#include<iostream>

using namespace std;
using ll = long long;

int main() {
	int a,b;
	cin >> a >> b;
	if ((a + b) % 2 == 0) {
		cout << (a + b) / 2 << endl;
	}
	else {
		cout << "IMPOSSIBLE" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
    string S,T,U;
    int A,B;
    cin>> S>>T;
    cin>>A>>B;
    cin>>U;
    if(U==S) A=A-1;
    else B=B-1;
    cout<< A<<" "<<B;
    return 0;
}


Measured memory_bytes: 256
#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>
#include <iomanip>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#include <complex>
#include <cstdio>
#include <list>
#include <bitset>

//< in.txt > out.txt
using namespace std;
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);
const long long MOD = 1e9 + 7;
const long long INF = 1e18;
typedef long long LL;
typedef long double LD;
typedef pair<LL, LL> PLL;
typedef pair<LD, LL> pdl;
typedef pair<LD, LD> pdd;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef unsigned long long ULL;
//typedef boost::multiprecision::cpp_int bigint;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	LL A, B, C, D;
	cin >> A >> B >> C >> D;
	while (true) {
		C -= B;
		if (C <= 0) {
			cout << "Yes\n";
			return 0;
		}
		A -= D;
		if (A <= 0) {
			cout << "No\n";
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 3132
/* 
	Author: ankrypt
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define MOD 1000000007
#define ll long long int
#define u64 unsigned long long int
#define ff first
#define ss second
#define all(x) x.begin(), x.end() 
#define ub upper_bound
#define lb lower_bound
#define MAX_INT 15
#define fi(a, b, c, d) for(int a = b; a < c; a += d)
#define fl(a, b, c, d) for(ll a = b; a < c; a += d)
#define fei(a, b, c, d) for(int a = b; a <= c; a += d)
#define fel(a, b, c, d) for(ll a = b; a <= c; a += d)
#define quit exit(0)

ll N, M, A, B, C;
ll arr[MAX_INT], arr1[MAX_INT], data[MAX_INT];
vector<ll> V;
map<string, ll> mp;
string S = "";

int main() {
	scanf("%lld", &N);
	fi(i, 0, N, 1) {
		cin >> S;
		mp[S]++;
	}
	cout << mp.size() << " \n";
	return 0;
}
/*
	Powered by Buggy Plugin
*/




Measured memory_bytes: 19288
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)) {
			// 文字列の入力
			String s = sc.next();
			for (int i = 0; i < s.length(); i++) {
				if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {
					System.out.println("No");
					System.exit(0);
				}
			}
			for (int i = 0; i < (s.length() / 2); i++) {
				if (s.charAt(i) != s.charAt((s.length() / 2) - 1 - i)) {
					System.out.println("No");
					System.exit(0);
				}
			}
			System.out.println("Yes");
		}
	}

	/**
	 * 最小公倍数
	 */
	static long lcm(long a, long b) {
		long temp;
		long c = a;
		c *= b;
		while ((temp = a % b) != 0) {
			a = b;
			b = temp;
		}
		return c / b;
	}

	/**
	 * 最大公約数
	 */
	static long gcd(long a, long b) {
		long temp;
		while ((temp = a % b) != 0) {
			a = b;
			b = temp;
		}
		return b;
	}
}


Measured memory_bytes: 21972
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<ll,ll> P;
#define M 1000000007
int main(){
  int n,a;
  cin>>n;
  vector<int> b;
  for(int i=0;i<n;i++){
    cin>>a;
    if(i==0) b.push_back(a);
    else{
      if(b[b.size()-1]<a)b[b.size()-1]=a;
      else if(b[0]>=a){
        b.insert(b.begin(),a);
      }else{
        b[lower_bound(b.begin(),b.end(),a)-b.begin()-1]=a;
      }
    }
  }
  cout<<b.size();
}

Measured memory_bytes: 892
#include <stdio.h>
#include <iostream>
#include <cstring>
using namespace std;

#define maxn 1005

// char str1[maxn];
// char str2[maxn];

string str1,str2;

int main(int argc, char const *argv[])
{

	cin>>str1>>str2;
	int len=str1.size();

	for (int i = 0; i < len/2; ++i){
		char t=str1[i];
		str1[i]=str1[len-i-1];
		str1[len-i-1]=t;
	}

	bool isRight=true;
	for (int i = 0; i < len; ++i){
		if(str1[i]!=str2[i]) isRight=false;
	}
	
	if(isRight) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;





	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(int argc, const char *argv[])
{
  long long w, h, x, y;
  cin >> w >> h >> x >> y;
  cout << w * h / 2.0 << " ";
  cout << (x * 2 == w && y * 2 == h ? 1 : 0) << "\n";
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include<string.h>
#define ll long long 
#include<vector>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int main(){
	IOS;
	int x,y,z;
	cin>>x>>y>>z;
	cout<<z<<" "<<x<<" "<<y;
	
	}

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

using namespace std;

const int MX = 100;

int a[MX];

int main() {
	int n, x;
	ignore = scanf("%d %d", &n, &x);
	for (int i = 0; i < n; i++) ignore = scanf("%d", a + i);
	
	sort(a, a + n);
	
	int ans = 0;
	while (ans < n && a[ans] <= x) x -= a[ans++];
	
	if (ans == n && x > 0) ans--;
	
	printf("%d\n", ans);
	
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#define rep(i,n) for (int i = 0; i < n; ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  int N, L;
  cin >> N >> L;
  int sum = 0;
  int eat = 9999999;
  rep(i,N) {
    int temp = L + i;
    if (abs(temp) < abs(eat)) eat = temp;
    sum += temp;
  }
  int ans = sum - eat;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3096
#include <bits/stdc++.h>
#define mod 1000000007
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define mkp make_pair
typedef long long ll;
using namespace std;

ll L, R;

int main() {
	cin >> L >> R;
	if (L + 2222 <= R) {
		cout << 0 << endl;
	}
	else {
		ll res = 2020;
		for (ll i = L; i <= R; ++i) {
			for (ll j = i + 1; j <= R; ++j) {
				res = min(i*j % 2019, res);
			}
		}
		cout << res << endl;
	}
}

Measured memory_bytes: 256
/*
 * http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_11_A
 */
#include <iostream>
#include <vector>
#include <map>

using namespace std;

class Die
{
    enum fname {
        top, front, right, left, back, bottom,
    };

    vector<int> faces;
    map<fname, int> f2i;

    void
    turn_e() {
        int tmp = f2i[top];
        f2i[top] = f2i[left];
        f2i[left] = f2i[bottom];
        f2i[bottom] = f2i[right];
        f2i[right] = tmp;
    }

    void
    turn_n() {
        int tmp = f2i[top];
        f2i[top] = f2i[front];
        f2i[front] = f2i[bottom];
        f2i[bottom] = f2i[back];
        f2i[back] = tmp;
    }

    void
    turn_s() {
        int tmp = f2i[top];
        f2i[top] = f2i[back];
        f2i[back] = f2i[bottom];
        f2i[bottom] = f2i[front];
        f2i[front] = tmp;
    }

    void
    turn_w() {
        int tmp = f2i[top];
        f2i[top] = f2i[right];
        f2i[right] = f2i[bottom];
        f2i[bottom] = f2i[left];
        f2i[left] = tmp;
    }

public:
    Die()
    {
        faces.reserve(6);

        f2i.emplace(top, 0);
        f2i.emplace(front, 1);
        f2i.emplace(right, 2);
        f2i.emplace(left, 3);
        f2i.emplace(back, 4);
        f2i.emplace(bottom, 5);
    }

    ~Die()
    {
        faces.clear();
        f2i.clear();
    }

    void
    read_faces(istream &is) {
        for (int i = 0; i < 6; i++) {
            is >> faces[i]; is.ignore();
        }
    }

    void
    turn(const char c) {
        switch (c) {
          case 'N':
            turn_n();
            break;
          case 'E':
            turn_e();
            break;
          case 'S':
            turn_s();
            break;
          case 'W':
            turn_w();
            break;
        }
    }

    int Top()    { return faces[f2i[top]   ]; }
    int Front()  { return faces[f2i[front] ]; }
    int Right()  { return faces[f2i[right] ]; }
    int Left()   { return faces[f2i[left]  ]; }
    int Back()   { return faces[f2i[back]  ]; }
    int Bottom() { return faces[f2i[bottom]]; }
};

int
main()
{
    ios::sync_with_stdio(false);

    Die d;
    d.read_faces(cin);

    string line;
    getline(cin, line);
    for (auto &it : line) {
        d.turn(it);
    }
    cout << d.Top() << endl;

    return 0;
}

Measured memory_bytes: 3168
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=n-1;i>=(0);i--)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define eall(v) unique(all(v), v.end())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll INFF = 1e18;


int main(void) {
	string s; cin >> s;
	int a = 0;
	for(auto u : s) if(u == '1')a++;
	printf("%d\n", a);
	return 0;
}

Measured memory_bytes: 256
#include <cstdlib>
#include <queue>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

typedef long long ll;

#include <cstdio>
inline int getInt(){ int s; scanf("%d", &s); return s; }
inline ll getLL(){ ll s; scanf("%lld", &s); return s; }

#include <set>

using namespace std;

int main(){
  const int a = getInt();
  const int b = getInt();
  const int q = getInt();

  vector<ll> s(a);
  vector<ll> t(b);
  REP(i,a) s[i] = getLL();
  REP(i,b) t[i] = getLL();

  REP(_,q){
    const ll x = getLL();

    vector<ll> ss;
    vector<ll> tt;

    auto sp = lower_bound(s.begin(), s.end(), x);
    auto tp = lower_bound(t.begin(), t.end(), x);

    if(sp != s.end()) ss.push_back(*sp);
    if(tp != t.end()) tt.push_back(*tp);

    if(sp != s.begin()) ss.push_back(*--sp);
    if(tp != t.begin()) tt.push_back(*--tp);

    ll ans = 1ll << 60;
    for(ll i : ss){
      for(ll j : tt){
	ans = min(ans, std::abs(i - j) + min(std::abs(i - x), std::abs(j - x)));
      }
    }

    printf("%lld\n", ans);
  }

  return 0;
}

Measured memory_bytes: 2816
#include <bits/stdc++.h>
using namespace std;using ll=int_fast64_t;using ld=long double;using pll=pair<ll,ll>;using pld=pair<ld,ld>;
const ll INF=1LL<<60;void solve();int main(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(10);solve();}
#define foreach(i,a) for(auto &i:a)
#define SELECTOR(_1,_2,_3,_4,SELECT,...) SELECT
#define rep(...) SELECTOR(__VA_ARGS__,_rep2,_rep1,_rep0)(__VA_ARGS__)
#define _rep0(i,n) for(ll i=0;i<n;++i)
#define _rep1(i,k,n) for(ll i=k;i<n;++i)
#define _rep2(i,k,n,d) for(ll i=k;d!=0&&d>0?i<n:i>n;i+=d)
template<class T> vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<class... Ts> auto make_v(size_t a,Ts... ts){return vector<decltype(make_v(ts...))>(a,make_v(ts...));}
template<class T> inline bool chmax(T &a,const T &b){if(a<b){a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a,const T &b){if(a>b){a=b; return 1;} return 0;}

class RollingHash{
private:
  ll b1=1007,b2=1009;
  ll m1=1e9+9, m2=1e9+7;
  vector<ll> H1,H2,P1,P2;
public:
  RollingHash(string S){
    ll n=(ll)S.size();
    H1.assign(n+1,0); H2.assign(n+1,0); P1.assign(n+1,1); P2.assign(n+1,1);
    rep(i,n){
      H1[i+1]=(H1[i]*b1+S[i])%m1;
      H2[i+1]=(H2[i]*b2+S[i])%m2;
      P1[i+1]=P1[i]*b1%m1;
      P2[i+1]=P2[i]*b2%m2;
    }
  }
  pair<ll,ll> hash(ll l,ll r){
    assert(l<=r);
    ll h1=H1[r]-P1[r-l]*H1[l]%m1;
    ll h2=H2[r]-P2[r-l]*H2[l]%m2;
    return {h1>=0?h1:h1+m1,h2>=0?h2:h2+m2};
  }
};

template<class T,class F>
constexpr T bisection(T l,T r,F f,bool left=true,bool discrete=true){
  T eps=discrete?1:pow(10,-12);
  if((!left)^f(r)) return left?r:r+1;
  if(left^f(l)) return left?l-1:l;
  while(r-l>eps){
    T h=(l+r)/2;
    (((!left)^f(h))?l:r)=h;
  }
  return discrete?left?l:r:(l+r)/2;
}

void solve(){
  ll n; cin>>n;
  string S; cin>>S;
  RollingHash rh{S};

  auto check=[&](ll k){
    map<pll,ll> mp;
    rep(i,n-k+1){
      pll h=rh.hash(i,i+k);
      if(mp.count(h)){ // 既に h が存在する場合
        if(i-mp[h]>=k) return true;
      }else{
        mp[h]=i;
      }
    }
    return false;
  };

  cout<<bisection((ll)0,n,check)<<"\n";
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
// using vi = vector<int>;
// using vvi = vector<vi>;
#define ote(x) cout<<(x)<<endl
#define all(x) (x).begin(),(x).end()
#define rp(i,s,e) for(int i=(s);i<(e);++i)

int N;
vl A;

vl solve(){
	// cout<<N<<"\n";//
	// for(auto x:A) cout<<x<<" ";puts("");//

	map<int,int> m;//<ai,count>
	rp(i,0,N) m[A[i]]++;

	// for(auto x:m){cout<<x.first<<" "<<x.second<<"\n";}//

	vl ruiseki(N+1);
	for(auto x:m){
		ll a,c; tie(a,c) = x;
		if(c>=2) ruiseki[a] = c*(c-1)/2;
	}

	// for(auto x:ruiseki){cout<<x<<" ";}puts("");//

	rp(i,1,ruiseki.size()){
		ruiseki[i] += ruiseki[i-1];
	}

	// for(auto x:ruiseki){cout<<x<<" ";}puts("");//

	vl del(N+1);
	for(auto x:m){
		ll a,c; tie(a,c) = x;
		if(c>=2) del[a] = (c-1)*(c-2)/2;
	}

	// for(auto x:del){cout<<x<<" ";}puts("");//

	vl ans(N, 0);
	rp(k,0,N){
		int ak = A[k];
		ll m = del[ak];
		ll f = 0 <= ak-1? ruiseki[ak-1]: 0;
		ll b = ruiseki[ruiseki.size()-1] - ruiseki[ak];
		ans[k] = f + m + b;
	}

	return ans;
}

int main(){
	cin>>N;
	A.resize(N);
	rp(i,0,N){cin>>A[i]; A[i]--;}
	for(auto x:solve()) cout<<x<<endl;
}


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

using namespace std;
typedef long long ll;

const int MAXN = 1e5;

int gcd(int, int);

char s[MAXN + 1], t[MAXN + 1];
map<ll, char>icMap;

int main() {
  int n, m;
  cin >> n >> m;
  ll lcm = (ll)n * m / gcd(n, m);
  cin >> s >> t;
  for (int i = 0; i < n; i++) icMap[i * (lcm / n) + 1] = s[i];
  for (int i = 0; i < m; i++) {
    int x = i * (lcm / m) + 1;
    if (icMap[x] && icMap[x] != t[i]) {
      cout << "-1" << endl;
      return 0;
    }
    icMap[x] = t[i];
  }
  cout << lcm << endl;
  return 0;
}

int gcd(int a, int b) {
  if (!b) return a;
  return gcd(b, a % b);
}


Measured memory_bytes: 10880
#include<cstdio>
#include<iostream>
#include<fstream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define Set(a) memset(a,0,sizeof(a))
#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define openf(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define re register
#define ri re int
#define il inline
typedef long long ll;
typedef unsigned long long ull;
template<typename T> inline T rd(T& x)
{
	T f=1;x=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(T)(c-'0');
	x*=f;
	return x;
}
ll rd(){ll x;rd(x);return x;}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
const int inf=1<<30;

char s[200005];ll cnt[2019];
int main()
{
	scanf("%s",s+1);
	int n=strlen(s+1);
	int now=0,base=1;cnt[0]=1;
	UF(i,n,1)
	{
		now=(now+(s[i]-'0')*base)%2019;
		cnt[now]++;base=base*10%2019;
		//cout<<now<<endl;
	}
	ll ans=0;
	F(i,0,2018) ans+=cnt[i]*(cnt[i]-1)/2;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3860
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int>P;
struct edge{
    int to,cap,cost,rev;
    edge(){}
    edge(int to,int cap,int cost,int rev):to(to),cap(cap),cost(cost),rev(rev){}
  };
struct PrimalDual{
  const int INF = 1<<28;
  typedef pair<int,int> P;

  int n;
  vector<vector<edge> > G;
  vector<int> h,dist,prevv,preve;

  PrimalDual(){}
  PrimalDual(int sz):n(sz),G(sz),h(sz),dist(sz),prevv(sz),preve(sz){}
  
  void add_edge(int from,int to,int cap,int cost){
    G[from].push_back(edge(to,cap,cost,G[to].size()));
    G[to].push_back(edge(from,0,-cost,G[from].size()-1));
  }

  int flow(int s,int t,int f){
    int res=0;
    fill(h.begin(),h.end(),0);
    while(f>0){
      priority_queue<P,vector<P>,greater<P> > que;
      fill(dist.begin(),dist.end(),INF);
      dist[s]=0;
      que.push(P(0,s));
      while(!que.empty()){
        P p=que.top();que.pop();
        int v=p.second;
        if(dist[v]<p.first) continue;
        for(int i=0;i<(int)G[v].size();i++){
          edge &e=G[v][i];
          if(e.cap>0&&dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){
            dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];
            prevv[e.to]=v;
            preve[e.to]=i;
            que.push(P(dist[e.to],e.to));
          }
        }
      }
      if(dist[t]==INF) return -1;
      for(int v=0;v<n;v++) h[v]+=dist[v];
      int d=f;
      for(int v=t;v!=s;v=prevv[v]){
        d=min(d,G[prevv[v]][preve[v]].cap);
      }
      f-=d;
      res+=d*h[t];
      for(int v=t;v!=s;v=prevv[v]){
        edge &e=G[prevv[v]][preve[v]];
        e.cap-=d;
        G[v][e.rev].cap+=d;
      }
    }
    return res;
  }
};

int a[111][111],b[111][111],n,ans,cnt;
string s[111];
signed main(){
  vector<P>er,wr;
  set<P>used;
  cin>>n;
  PrimalDual p(n*2+2);
  int x=n*2,y=n*2+1;
  r(i,n)r(j,n)cin>>a[i][j];
  r(i,n)r(j,n)cin>>b[i][j];
  r(i,n)cin>>s[i];
  r(i,n)r(j,n){
    if(s[i][j]=='o'){
      p.add_edge(i,n+j,1,-b[i][j]);
      ans+=b[i][j];
      er.push_back(P(i,j));
    }
    else p.add_edge(i,n+j,1,a[i][j]);
  }
  r(i,n)p.add_edge(x,i,1,0);
  r(i,n)p.add_edge(i+n,y,1,0);
  cout<<ans+p.flow(x,y,n)<<endl;
  r(i,n){
    vector<edge>v=p.G[i];
    r(j,n){
      if(v[j].cap==0){
        if(v[j].cost<0)used.insert(P(i,j));
        else wr.push_back(P(i,j));
      }
    }
  }
  r(i,er.size()){
    if(used.count(er[i]))continue;
    cnt++;
  }
  cout<<cnt+wr.size()<<endl;
  r(i,er.size()){
    if(used.count(er[i]))continue;
    cout<<er[i].first+1<<' '<<er[i].second+1<<' '<<"erase"<<endl;
  }
  r(i,wr.size()){
    cout<<wr[i].first+1<<' '<<wr[i].second+1<<' '<<"write"<<endl;
  }
}


Measured memory_bytes: 3508