akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cctype>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cstring>
#include <string>
#include <sstream>
#include <algorithm>
#include <iomanip>
using namespace std;

typedef vector<int> VI;
typedef vector<VI> VII;
typedef pair<int, int> PII;
typedef long long ll;

#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back;
#define MP make_pair
#define SIZE(a) int((a).size())
#define SORT(c) sort((c).begin(), (c).end())

const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = INT_MAX / 3;

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

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int main(void){
  string in;
  while(cin >> in){
    int joi = 0, ioi = 0;
    for(int i = 0; i < in.size(); i++){
      string n(in, i, 3);
      if(n == "JOI") joi++;
      if(n == "IOI") ioi++;
      if(i == in.size() - 4) break;
    }
    cout << joi << endl;
    cout << ioi << endl;
  }
  return 0;
}

Measured memory_bytes: 1212
#include <stdio.h>

#define N 16

static
int reconf (
  int * a,
  int   n
  )
{
  int d[ N ];
  int res = 1;
  int i, j;

  for ( i = 0; i < n; ++i )
  {
    d[ i ] = a[ i ];
  }

  for ( j = 0; j < n; ++j )
  {
    a[ j ] = 0;
    for ( i = 0; i < n; ++i )
    {
      a[ j ] += !!( d[ i ] == d[ j ] );
    }
  }

  for ( i = 0; i < n; ++i )
  {
    res = res && ( a[ i ] == d[ i ] );
  }

  return ( res );
}

/** Application main entry point. */
int main (
  int     argc,
  char  * argv[ ]
  )
{
  int i;

  for ( ; ; )
  {
    int d[ N ];
    int res = 0;
    int n;

    scanf ( "%d", &n );
    if ( !( n ) ) break ;

    for ( i = 0; i < n; ++i )
    {
      scanf ( "%d", d + i );
    }

    while ( !reconf ( d, n ) ) ++res;

    printf ( "%d\n", res );
    for ( i = 0; i < n; ++i )
    {
      if ( i )  putchar ( ' ' );
      printf ( "%d", d[ i ] );
    }
    puts ( "" );
  }

  return ( 0 );
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <cstdio>
#include <deque>
#include <algorithm>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <stack>

using namespace std;
int n, k;
int c[100001];
pair<long long, int> a[100001];
vector<pair<long long, int>> v;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> a[i].second >> a[i].first;
	}
	priority_queue<pair<long long, pair<int,int>>> q;
	long long ans = 0;
	sort(a, a + n);
	long long s = 0;
	for (int i = n - 1; i >= 0; i--) {
		if (c[a[i].second] == 0) {
			c[a[i].second] = 1;
			if (s < k) {
				ans += a[i].first;
				s += 1;
				v.push_back({ a[i].first,i });
			}
		}
		else {
			q.push({ a[i].first,{a[i].second,i} });
		}
	}

	ans += s * s;
	int t = s;
	while (t < k) {
		ans += q.top().first;
		c[q.top().second.first] += 1;
		v.push_back({ q.top().first,q.top().second.second });
		q.pop();
		t += 1;
	}

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

	long long cnt = ans;
	for (int i = 0; i < v.size(); i++) {
		if (q.empty())break;
		if (c[a[v[i].second].second] - 1 > 0) {
			if (c[q.top().second.first] == 0) {
				long long temp = cnt - s * s - a[v[i].second].first + q.top().first + (s + 1)*(s + 1);
				if (temp > cnt) {
					cnt = temp;
					c[q.top().second.first] += 1;
					s += 1;
				}
				else {
					c[a[v[i].second].second] += 1;
					continue;
				}
			}
			else {
				long long temp = cnt - a[v[i].second].first + q.top().first;
				if (temp > cnt) {
					cnt = temp;
					c[q.top().second.first] += 1;
				}
				else {
					c[a[v[i].second].second] += 1;
					continue;
				}
			}
			q.pop();
			ans = max(ans, cnt);
		}
		else {
			c[a[v[i].second].second] -= 1;
			if (c[a[v[i].second].second] == 0) {
				if (c[q.top().second.first] == 0) {
					long long temp = cnt - a[v[i].second].first + q.top().first;
					if (temp > cnt) {
						c[q.top().second.first] += 1;
						cnt = temp;
					}
					else {
						c[a[v[i].second].second] += 1;
						continue;
					}
				}
				else {
					long long temp = cnt - s * s - a[v[i].second].first + q.top().first + (s - 1)*(s - 1);
					if (temp > cnt) {
						cnt = temp;
						s -= 1;
						c[q.top().second.first] += 1;
					}
					else {
						c[a[v[i].second].second] += 1;
						continue;
					}
				}
			}
			else {
				if (c[q.top().second.first] == 0) {
					long long temp = cnt - s * s - a[v[i].second].first + q.top().first + (s + 1)*(s + 1);
					if (temp > cnt) {
						cnt = temp;
						c[q.top().second.first] += 1;
						s += 1;
					}
					else {
						c[a[v[i].second].second] += 1;		
						continue;
					}
				}
				else {
					long long temp = cnt - a[v[i].second].first + q.top().first;
					if (temp > cnt) {
						cnt = temp;
						c[q.top().second.first] += 1;
					}
					else {
						c[a[v[i].second].second] += 1;
						continue;
					}
				}
			}
			q.pop();
			ans = max(ans, cnt);
		}
	}
	cout << ans << '\n';
}


Measured memory_bytes: 4980
#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  

#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")  
using namespace std;

#define mp make_pair  
#define Fi first  
#define Se second  
#define pb(x) push_back(x)  
#define szz(x) ((int)(x).size())  
#define rep(i, n) for(int i=0;i<n;i++)  
#define all(x) (x).begin(), (x).end()  
#define ldb ldouble  

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 19;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;

ll getv(ll x) {
	ll t = x, s = 0;
	while (t) {
		s += t % 10;
		t /= 10;
	}
	return s;
}
int main() {
	vector <ll> Vl;

	ll i, j, k;
	for (i = 1; i <= 8; i++) Vl.push_back(i);

	ll cur = 9;
	for (i = 1; i <= 15; i++) {
		Vl.push_back(cur);
		for (j = 1;; j++) {
			if (j % 10 == 9) continue;
			if (j >= getv(j) + 9 * i) break;
			Vl.push_back((cur + 1) * j + cur);
		}
		cur = cur * 10 + 9;
	}
	sort(all(Vl));


	int N;
	scanf("%d", &N);
	for (i = 0; i < N; i++) printf("%lld\n", Vl[i]);
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>

using namespace std;

#define mod 1000000007


int main()
{
	int n;
	cin >> n;
	int ans = 0;
	for(int i = 1; i <= n; i += 2){
		int cnt = 0;
		for(int j = 1; j <= i; j++){
			if(i % j == 0) cnt++;
		}
		if(cnt == 8) ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <string>
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <math.h>
 
using namespace std;
int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
 
	int h1,h2,m1,m2,k,one,two,three;
	cin >> h1 >> m1 >> h2 >> m2 >>k;
    one = 60*(h2-h1);
    two = m2-m1;
    three = one + two -k;
     cout << three << "\n";
}

Measured memory_bytes: 3600
// you**can**do**anything :~  
#include <bits/stdc++.h>
#include<iostream> 
#include<algorithm> 
#include<vector> 
#define ll long long
//#define  loop(y)  for((int)i=0 ; i<int(y) ,i++)
const int maxn=5e5+10;
using namespace std;
int main() {
cin.tie(0); cout.tie(0);
//ios_base :: sync_with_stdio( 0 ) ;
 double i=0;
 cin>>i;
 i*=6.28318530717958623200;
 printf("%.10f" , i);
 



}

Measured memory_bytes: 3788
#include <stdio.h>

int main(void)
{
	char str[1001];
	int i = 0;
	
	scanf("%[^\n]", str);
	
	for (i = 0; str[i] != '\0'; i++){
		if ((str[i] == 'a') && (str[i + 1] == 'p') && (str[i + 2] == 'p') && (str[i + 3] == 'l') && (str[i + 4] == 'e')){
			str[i + 0] = 'p';
			str[i + 1] = 'e';
			str[i + 2] = 'a';
			str[i + 3] = 'c';
			str[i + 4] = 'h';
			i += 4;
		}
		if ((str[i] == 'p') && (str[i + 1] == 'e') && (str[i + 2] == 'a') && (str[i + 3] == 'c') && (str[i + 4] == 'h')){
			str[i + 0] = 'a';
			str[i + 1] = 'p';
			str[i + 2] = 'p';
			str[i + 3] = 'l';
			str[i + 4] = 'e';
			i += 4;
		}
	}
	
	printf("%s\n", str);
	
	return (0);
}
		

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,n) for(int i=(a); i<(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;

ll dp[110][100010];
int w[110];
int v[110];

int main() {
	int N, W; cin >> N >> W;
	rep(i, N) cin >> w[i] >> v[i];

	// dp[i+1][sum_w] = max(dp[i][sum_w], dp[i][sum_w-w]+v);
	rep(i, N) rep(sum_w, W+1) {
		int weight = w[i];
		int value = v[i];
		if (sum_w>=weight) dp[i+1][sum_w] = max(dp[i][sum_w], dp[i][sum_w-weight]+value);
		else dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w]);
	}

	// rep(i, N+1) rep(j, W+1) cout << "i " << i <<" j " << j << " " << dp[i][j] << endl;
	cout << dp[N][W] << endl;
}

Measured memory_bytes: 79360
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	int d[105];
	for(int i=0;i<n;i++) cin>>d[i];
	int sum=0,x;
	for(int i=0;i<n;i++){
		x=i;
		if(x==n-1) break;
		for(int j=x+1;j<n;j++) sum+=d[x]*d[j];
	}
	cout<<sum<<endl;
	return 0;
}


Measured memory_bytes: 256
import Control.Monad
import Control.Applicative
import Data.Functor
import Data.Function
import Data.Monoid
import Data.Maybe
import Data.List
import Data.Foldable (foldMap)
import Data.List.Split
import Data.Char
import Data.Ratio
import Data.Ord
import Data.Array.IO
 
readInt = read :: String -> Int
readDouble = read :: String -> Double
getInt = readLn :: IO Int
getInts = map readInt . words <$> getLine
sjoin :: (Show a) => [a] -> String
sjoin = unwords . map show
cond :: a -> a -> Bool -> a
cond t f c = if c then t else f
-- end of templete

main = map ((*7.814814814814815) . read) . lines <$> getContents >>= mapM_ print

Measured memory_bytes: 4360
n, m = map(int, input().split())
ab = sorted(list(map(int, input().split())) for _ in range(m))


def dfs(now, count):
    if count <= 2 and visit[n] == 0:
        visit[now] = 1
        if count <= 1:
            for x in graph[now]:
                dfs(x, count + 1)


flag = False
if ab[0][0] == 1:
    graph = [[] for _ in range(n + 1)]
    for a, b in ab:
        graph[a].append(b)
        graph[b].append(a)

    visit = [0] * (n + 1)
    dfs(1, 0)

    if visit[n] == 1:
        flag = True

print('POSSIBLE') if flag else print('IMPOSSIBLE')


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

int main() {
	int Zx, Xy, Yz = 0;
	char Xz[14];
	scanf("%d %d", &Zx, &Xy);
	scanf("%s", &Xz);
	int lng = strlen(Xz);
	for (int u = 0; u < lng; u++) {
		if (Xz[Zx] != '-') {
			printf("No");
			return 0;
		}
		if ('0' <= Xz[u] && Xz[u] <= '9') {
			Yz++;
		}
	}
	if (Yz != (Zx + Xy)) {
		printf("No");
		return 0;
	}
	printf("Yes\n");
	return 0;	
}

Measured memory_bytes: 1696
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;bool f=1;char c=getchar();
    if(c==EOF) return 0;
    while(c<'0' || c>'9'){if(c=='-') f=0;c=getchar();}
    while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?x:-x;
}
struct node
{
    int st,ed;
    bool operator < (const node &x)const
    {
        return ed<x.ed;
    }
}a[100010];
int n,t,ans=1;
int main()
{
    n=read();
    for(int i=0;i<n;i++)
    {
        int x=read(),l=read();
        a[i].st=x-l;
        a[i].ed=x+l;
    }
    sort(a,a+n);
    t=a[0].ed;
    for(int i=1;i<n;i++)
    {
        if(a[i].st>=t)
        {
            ans++;
            t=a[i].ed;
        }
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define il inline
#define db double
#define ls rt << 1
#define rs rt << 1 | 1
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define X first
#define Y second
#define pcc pair<char, char>
#define vi vector<int>
#define vl vector<ll>
#define rep(i, x, y) for(int i = x; i <= y; i ++)
#define rrep(i, x, y) for(int i = x; i >= y; i --)
#define rep0(i, n) for(int i = 0; i < (n); i ++)
#define per0(i, n) for(int i = (n) - 1; i >= 0; i --)
#define ept 1e-9
#define INF 0x3f3f3f3f
#define sz(x) (x).size()
#define All(x) (x).begin(), (x).end()
#define lowbit(x) ((x) & -(x))
using namespace std;
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
inline ll read1()
{
	ll x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
const ll mod = 1e9 + 7;
const int N = 4e6 + 10;
const db pi = acos(-1);
//int a[N];
int main()
{
	int n = read();
	vi a(n);
	rep0(i, n) a[i] = read();
	int q = read();
	while(q --)
	{
		int x = read();
		int y = read();
		int z = read();
		swap_ranges(a.begin() + x, a.begin() + y, a.begin() + z);
	} 
	rep0(i, n)
	{
		if(i) cout << " ";
		cout << a[i];
	}
	puts("");
	return 0;
}



Measured memory_bytes: 3104
#include <bits/stdc++.h>
#define rep(i, a) for(int i = 0; i < a; i++)
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> l(n);
    rep(i, n) {
        cin >> l[i];
    }
    sort(l.begin(), l.end());
    int a = 0;
    rep(i, n - 1) a += l[i];
    cout << ((l[n - 1] < a) ? "Yes" : "No") << endl;
}

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

#define speed ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define test ll t; cin>>t; while(t--)
#define ll long long
#define endl "\n"
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define pb push_back
#define PI 3.1415926535897932384626
#define inf 1e18
#define vll vector<ll>
#define forn(i,n) for (int i = 0; i < int(n); i++)
#define fl(i,a,b) for(ll i=a;i<b;i++)
#define flr(i,a,b) for(ll i=a;i>b;i--)
#define print(v) for(auto i=v.begin();i!=v.end();i++){cout<<*i<<" ";}cout<<"\n";
#define MOD 1000000007

bool palindrome(string str){
	ll n = str.length();
	for(ll i=0, j = n-1; i<=j;++i,--j){
		if(str[i]!=str[j])
			return false;
	}
	return true;
}

int main()
{
    speed;
    string s;
    cin>>s;
    ll len = s.length();
    string st1,st2;
    st1 = s.substr(0,(len-1)/2);
    st2 = s.substr((len+3)/2-1,len);
    //cout<<s<<endl<<st1<<endl<<st2<<endl;
    if(palindrome(s)&&palindrome(st1)&&palindrome(st2))
    	cout<<"Yes"<<endl;
    else
    	cout<<"No"<<endl;
    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);
		while (true) {
			int H = sc.nextInt();
			int W = sc.nextInt();
			if (H == 0 && W == 0) {
				break;
			} else {
				for (int i = 0; i < H; ++i) {
					for (int j = 0; j < W; ++j) {
						System.out.print("#");
					}
					System.out.print("\n");
				}
			}
			System.out.print("\n");
		}
		sc.close();
	}

}



Measured memory_bytes: 36560
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define gt getchar()
#define ll long long
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
typedef std::pair<int,int> P;
#define mk std::make_pair
#define fr first
#define sc second
inline int in()
{
	int k=0;char ch=gt;bool p=1;
	while(ch<'-')ch=gt;if(ch=='-')ch=gt,p=0;
	while(ch>'-')k=k*10+ch-'0',ch=gt;
	return p?k:-k;
}
const int N=4005;
int mp[N][N];char s[5];
int main()
{
	int n=in(),m=in(),k=in();
	s[1]='R',s[2]='Y',s[3]='B',s[4]='G';
	for(int i=1;i<=std::max(n,m)*4;++i)
		for(int j=1;j<=std::max(m,n)*4;++j)
		{
			int x=(i-1)/k+1,y=(j-1)/k+1;
			mp[i][j]=4-(x&1)*2-(y&1);
		}
	for(int i=1;i<=n;++i,puts(""))
		for(int j=1;j<=m;++j)
			putchar(s[mp[i+j+m][i-j+m]]);
	return 0;
}


Measured memory_bytes: 32640
#include<stdio.h>
int W[30001],S[30001],A,B,C,D,E,F,i,j,aw,as=-1,w,s;
main(){
scanf("%d%d%d%d%d%d",&A,&B,&C,&D,&E,&F);
for(i=0;i<=F;i+=100*A)for(j=0;i+j<=F;j+=100*B)W[i+j]=1;
for(i=0;i<=F;i+=C)for(j=0;i+j<=F;j+=D)S[i+j]=1;
for(w=0;w<=F;w++)for(s=0;w+s<=F;s++)if(W[w]&&S[s]&&s<=w/100*E&&s*aw>as*w)aw=w,as=s;
printf("%d %d\n",aw+as,as);
}

Measured memory_bytes: 128
#include <cstdlib>
#include <iostream>
#include <numeric>
#include <unordered_map>
#include <vector>
using namespace std;

template<class T> inline void chmin(T &a, const T &b) { if(a > b) a = b; }

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

	constexpr int INF = (1 << 25);

	for(int n; cin >> n && n;) {
		vector<vector<pair<string, int>>> supers(n);
		for(int i = 0; i < n; ++i) {
			int k;
			cin >> k;

			supers[i].reserve(k);
			while(k--) {
				string name;
				int value;
				cin >> name >> value;
				supers[i].emplace_back(name, value);
			}
		}

		int q;
		cin >> q;
		unordered_map<string, int> conv;

		for(int i = 0; i < q; ++i) {
			string name;
			cin >> name;
			conv.insert({name, i});
		}

		vector<vector<int>> costs(n, vector<int>(q, INF));
		for(int i = 0; i < n; ++i) {
			for(const auto &e : supers[i]) {
				if(conv.count(e.first)) {
					costs[i][conv[e.first]] = e.second;
				}
			}
		}

		int m;
		cin >> m;

		vector<vector<int>> mat(n + 1, vector<int>(n + 1, INF));
		while(m--) {
			int s, t, d;
			cin >> s >> t >> d;
			s = (s + n) % (n + 1);
			t = (t + n) % (n + 1);
			mat[s][t] = mat[t][s] = d;
		}

		for(int i = 0; i <= n; ++i) mat[i][i] = 0;
		for(int k = 0; k <= n; ++k) {
			for(int i = 0; i <= n; ++i) {
				for(int j = 0; j <= n; ++j) {
					chmin(mat[i][j], mat[i][k] + mat[k][j]);
				}
			}
		}

		int min_cost = INF, min_dist = INF;
		for(int i = 0; i < (1 << n); ++i) {
			vector<int> c(q, INF);
			for(int j = 0; j < n; ++j) {
				if(!(i & (1 << j))) continue;
				for(int k = 0; k < q; ++k) {
					chmin(c[k], costs[j][k]);
				}
			}

			const int sum_cost = accumulate(c.begin(), c.end(), 0);
			if(sum_cost <= min_cost) {
				if(sum_cost < min_cost) {
					min_cost = sum_cost;
					min_dist = INF;
				}

				vector<vector<int>> dp(n, vector<int>(i + 1, INF));
				for(int j = 0; j < n; ++j) {
					if(i & (1 << j)) {
						dp[j][1 << j] = mat[n][j];
					}
				}

				for(int k = 1; k < i; ++k) {
					if(!(i & k) || (~i & k)) continue;
					for(int j = 0; j < n; ++j) {
						if(dp[j][k] == INF) continue;
						for(int l = 0; l < n; ++l) {
							const int next_visited = (k | (1 << l));
							if(k == next_visited || (~i & next_visited)) continue;
							chmin(dp[l][next_visited], dp[j][k] + mat[j][l]);
						}
					}
				}

				int sum_dist = INF;
				for(int j = 0; j < n; ++j) {
					chmin(sum_dist, dp[j][i] + mat[j][n]);
				}
				chmin(min_dist, sum_dist);
			}
		}

		if(min_cost == INF) {
			cout << "impossible" << endl;
		}
		else {
			cout << min_cost << " " << min_dist << endl;
		}
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 1308
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = (1 << 30) - 1;
const ll infll = (1LL << 61) - 1;

#include <vector>
const long long mod = 1e9 + 7;
//a partition of n by k-th number
template <typename T>
vector<vector<T>> get_partition(int n, int k)
{
    vector<vector<T>> dp(n + 1, vector<T>(k + 1));
    dp[0][0] = 1;
    for (int i = 0; i <= n; i++)
    {
        for (int j = 1; j <= k; j++)
        {
            dp[i][j] = (dp[i][j - 1] + (i - j >= 0 ? dp[i - j][j] : 0)) % mod;
        }
    }
    return dp;
}

int main()
{
    int N, K;
    cin >> N >> K;
    cout << get_partition<ll>(N, K)[N][K] << endl;
}


Measured memory_bytes: 10796
n = int(input())
a_list = sorted(list(map(int, input().split(" "))))

i = 0
for target_val in range(1, n + 1):
    cnt = 0
    while target_val == a_list[min(i, len(a_list) - 1)] and i < len(a_list):
        i += 1
        cnt += 1
    print(cnt)


Measured memory_bytes: 32316
//  ____            _                  _                       _       _
// |  _ \ _   _ ___| |_    ___ _ __   | |_ ___ _ __ ___  _ __ | | __ _| |_ ___
// | |_) | | | / __| __|  / __| '_ \  | __/ _ \ '_ ` _ \| '_ \| |/ _` | __/ _ \
// |  _ <| |_| \__ \ |_  | (__| |_) | | ||  __/ | | | | | |_) | | (_| | ||  __/
// |_| \_\\__,_|___/\__|  \___| .__/___\__\___|_| |_| |_| .__/|_|\__,_|\__\___|
//                            |_| |_____|               |_|

//https://github.com/manta1130/Competitive_Programming_Template_Rust

#[macro_use]
mod input {

    use std;
    use std::io;

    const SPLIT_DELIMITER: char = ' ';

    #[macro_export]
    #[allow(unused_macros)]
    macro_rules! input {
    ( $($x:expr ),*) => {
        {
            let temp_str = input_line_str();
            let mut split_result_iter = temp_str.split_whitespace();
                $(
                let buf_split_result = split_result_iter.next();
                let buf_split_result = buf_split_result.unwrap();
                    ($x) = buf_split_result.parse().unwrap();
                )*
        }
    };
}

    #[allow(dead_code)]
    pub fn input_line_str() -> String {
        let mut s = String::new();
        io::stdin().read_line(&mut s).unwrap();
        s.trim().to_string()
    }

    #[allow(dead_code)]
    pub fn p<T>(t: T)
    where
        T: std::fmt::Display,
    {
        println!("{}", t);
    }

    #[allow(dead_code)]
    pub fn input_vector2d<T>(line: usize) -> Vec<Vec<T>>
    where
        T: std::str::FromStr,
    {
        let mut v: Vec<Vec<T>> = Vec::new();

        for _ in 0..line {
            let vec_line = input_vector();
            v.push(vec_line);
        }
        v
    }

    #[allow(dead_code)]
    pub fn input_vector<T>() -> Vec<T>
    where
        T: std::str::FromStr,
    {
        let mut v: Vec<T> = Vec::new();

        let s = input_line_str();
        let split_result = s.split(SPLIT_DELIMITER);
        for z in split_result {
            let buf = match z.parse() {
                Ok(r) => r,
                Err(_) => panic!("Parse Error"),
            };
            v.push(buf);
        }
        v
    }

    #[allow(dead_code)]
    pub fn input_vector_row<T>(n: usize) -> Vec<T>
    where
        T: std::str::FromStr,
    {
        let mut v = Vec::with_capacity(n);
        for _ in 0..n {
            let buf = match input_line_str().parse() {
                Ok(r) => r,
                Err(_) => panic!("Parse Error"),
            };
            v.push(buf);
        }
        v
    }

    pub trait ToCharVec {
        fn to_charvec(&self) -> Vec<char>;
    }

    impl ToCharVec for String {
        fn to_charvec(&self) -> Vec<char> {
            self.to_string().chars().collect::<Vec<_>>()
        }
    }
}

use input::*;

fn main() {
    let (s, t): (String, String);
    input!(s, t);
    let (mut a, mut b): (usize, usize);
    input!(a, b);
    let u = input_line_str();
    if u == s {
        a -= 1;
    } else {
        b -= 1;
    }
    println!("{} {}", a, b);
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
#define inf 1000000007

using namespace std;

typedef long long ll;

int k, n, a[200005], b0[200005], b1[200005];

void add(int *b,int i,int v)
{
    while(i<=n)
    {
        b[i]+=v;
        i+=(i&(-i));
    }
}

int sum(int *b,int i)
{
    ll s=0;
    while(i>0)
    {
        s+=b[i];
        i-=(i&(-i));
    }
    return s;
}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    int p=1;
    while(k--)
    {
        int v=0;
        for(int i=1;i<=n;i++)
        {
            int l=max(1,i-a[i]), r=min(n,i+a[i]);
            add(b0,l,-1*(l-1));
            add(b1,l,1);
            add(b0,r+1,1*r);
            add(b1,r+1,-1);
        }
        for(int i=1;i<=n;i++)
        {
            a[i]=(sum(b0,i)+sum(b1,i)*i)-(sum(b0,i-1)+sum(b1,i-1)*(i-1));
            if(a[i]==n)
                v++;
        }
        if(v==n)
        {
            p=0;
            break;
        }
        memset(b0,0,sizeof(b0));
        memset(b1,0,sizeof(b1));
    }
    if(p==0)
    {
        for(int i=1;i<=n;i++)
        printf("%d%c",n,i==n?'\n':' ');
    }
    else
    {
        for(int i=1;i<=n;i++)
        printf("%d%c",a[i],i==n?'\n':' ');
    }
    return 0;
}



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

int main() {
  
  int A, B; string S; cin >> A >> B >> S;
  
  bool flag = true;
  
  for (int i = 0; i < A; i++) {
    if (S.at(i) == '-') flag = false;
  }
  
  if (S.at(A) != '-') flag = false;
  
  for (int i = A + 1; i < S.size(); i++) {
    if (S.at(i) == '-') flag = false;
  }
  
  if (flag) cout << "Yes" << endl;
  
  else cout << "No" << endl;
  
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int X;
	int i;
	int anc = 1, test;
	
	scanf("%d", &X);
	
	if (X == 1){
		printf("1\n");
	}
	else {
		for (i = 2; i * i <= X; i++){
			test = i;
		 	while (test * i <= X){
		 		test *= i;
		 	}
		 	anc = test > anc ? test : anc;
		}
		printf("%d\n", anc);
	}
	
	return (0);
}

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

int main(){

  int n, y, m, d, total=0;
  cin >> n;

  for(int i=0; i<n; i++){
    cin >> y >> m >> d;
    if(y%3==0){
      total = (y-1)/3*590 + (y-1)%3*195 + (m-1)*20 + d;
    } else {
      total = (y-1)/3*590 + (y-1)%3*195 + m/2*20 + (m-1)/2*19 + d;
    }
    total = 196471 - total;
    cout << total << endl;
  }

  return 0;
}

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

#define dbg(a)  cerr << __LINE__ << ": " << #a << " = " << a << '\n'

template<class T> inline istream& operator>>(istream& str, vector<T> &a) { for (auto &i : a) str >> i; return str; }

typedef long long ll;

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  
  int n;  cin >> n;
  ll a[n];
  for (int i = 0; i < n; ++i){
    cin >> a[i];
  }
  ll price = a[0], now = 1000;
  for (int i = 0; i < n; ++i){
    if(a[i]>price){
      now += (now/price)*(a[i]-price);
      price = a[i];
    } else {
      price = min(price, a[i]);
    }
  }
  cout << now << "\n";
  return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1001001001;
const ll LINF = 1001001001001001;
const int MOD = 1000000007;

template <typename T>
void print(const T &v);

int main()
{
    int n;
    cin >> n;
    vector<ll> as(n);
    for (int i = 0; i < n; i++)
    {
        cin >> as[i];
    }
    as.push_back(as[0]);
    ll left = -1;
    ll right = 1000000001;
    while (right - left > 1)
    {
        ll mid = (left + right) / 2;
        ll x = mid;
        bool flag = true;
        vector<ll> ans;
        for (int i = 0; i < n; i++)
        {
            ans.push_back(x * 2);
            x = as[i] - x;
        }
        if (mid == x)
        {
            print(ans);
            return 0;
        }
        else if (mid < x)
        {
            left = mid;
        }
        else
        {
            right = mid;
        }
    }
    cout << "error" << endl;
    return 0;
}

// Use For Debug
template <typename T>
void print(T const &v)
{
    for (int i = 0; i < v.size(); i++)
    {
        if (i)
            cout << ' ';
        cout << v[i];
    }
    cout << endl;
};

Measured memory_bytes: 5828
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define rep(i,m,n) for(int i=(int)(m);i<(int)(n);++i)
#define rREP(i,m,n) for(int (i)=(n)-1; (i)>=(m);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr int INF = 1000000001;
constexpr ll mod = 1000000007;
constexpr double PI = 3.1415926535897932;

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;
}
inline void init() {
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

int main() {
	init();

	ll N, P; cin >> N >> P;
	map<ll, ll>mp;
	ll x = P;
	rep(i, 2, sqrt(x) + 1) {
		while (x % i == 0) {
			x /= i;
			mp[i]++;
		}
	}
	if (x > 1)mp[x]++;
	ll ans = 1;
	for (auto p : mp) {
		int a = p.second / N;
		rep(i, 0, a)ans *= p.first;
	}
	cout << ans << "\n";

	return 0;
}

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

int main()
{
  string s;
  cin >> s;
  size_t len = s.length();
  uint64_t count_b = 0;
  uint64_t ans = 0;
  for (auto i = 0; i < len; i++) {
    if (s[i] == 'B') {
      count_b++;
    } else {
      ans += count_b;
    }
  }
  cout << ans << endl;
}


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

int main(){
  int n, k;
  cin >> n >> k;
  vector<int> sunuke(n);
  for(int i = 0; i < k; ++i){
    int d;
    cin >> d;
    for(int j = 0; j < d; ++j){
      int a;
      cin >> a;
      sunuke.at(a-1)++;
    }
  }
  
  int ans = 0;
  for(auto a : sunuke){
    if(a) continue;
    ans++;
  }
  
  cout << ans << endl;
}


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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    string s;
    cin >> s;
    int q;
    cin >> q;
    string pref, suf;
    int flg = 0;
    while (q--) {
        int t; cin >> t;
        if (t == 1) flg = !flg;
        else {
            int f; char c;
            cin >> f >> c;
            if (flg) {
                if (f == 1) suf.push_back(c);
                else pref.push_back(c);
            }
            else {
                if (f == 1) pref.push_back(c);
                else suf.push_back(c);
            }
        }
    }
    if (flg) {
        for (int i = (int) suf.size() - 1; i >= 0; i--) cout << suf[i];
        reverse(s.begin(), s.end());
        cout << s;
        for (int i = 0; i < (int) pref.size(); i++) cout << pref[i];
        cout << '\n';
    }
    else {
        for (int i = (int) pref.size() - 1; i >= 0; i--) cout << pref[i];
        cout << s;
        for (int i = 0; i < (int) suf.size(); i++) cout << suf[i];
    }
}

Measured memory_bytes: 1040
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <list>
#include <numeric>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <ctime>
#include <cassert>

#define INF 1000000000
#define LINF 9000000000000000000
#define mod 1000000007

#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back
#define mp make_pair

using namespace std;

/*
   cin.tie(0);
   ios::sync_with_stdio(false);
   */

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<long long>vll;
typedef pair<int,int> pi;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[8]={-1,-1,0,1,1,1,0,-1};
int ddy[8]={0,1,1,1,0,-1,-1,-1};
bool debug=false;

/*---------------------------------------------------*/

int main(){
  int n,m,a[55],b[55];
  int ans[55];
  cin>>n>>m;
  for(int i=0;i<n;i++){
    ans[i]=0;
  }
  for(int i=0;i<m;i++){
    cin>>a[i]>>b[i];
    ans[a[i]-1]++;
    ans[b[i]-1]++;
  }
  for(int i=0;i<n;i++){
    cout<<ans[i]<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
//#include "stdc++.h"
#include<bits/stdc++.h>
#include<algorithm>
#include<unordered_map>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define ld long double

int main()
{
    ll n;
    cin>>n;
    ll a[n];
    for(ll i=0;i<n;i++)
    {
        cin>>a[i];
    }
    ll ans=0;
    for(ll i=1;i<n-1;i++)
    {
        if(a[i]>a[i-1] && a[i]<a[i+1])
        {
            ans++;
            continue;
        }
        if(a[i]<a[i-1] && a[i]>a[i+1])
        {
            ans++;
            continue;
        }
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 256
n, m = map(int, input().split())
x= list(map(int, input().split()))
x.sort()
diff = []
for i in range(m-1) :
    diff.append(x[i+1] - x[i])
diff.sort()

sum =0
for i in range(0,len(diff)-n+1) :
    sum += diff[i]

print (sum)

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

int w[10];
int k[10];
int main(){

for(int i=0;i<10;i++)cin>>w[i];
for(int i=0;i<10;i++)cin>>k[i];
sort(w,w+10);
sort(k,k+10);
cout<<(w[9]+w[8]+w[7])<<' '<<(k[9]+k[8]+k[7])<<endl;
 
return 0;
}



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


int main(int argc, char const *argv[])
{
	int n, k; cin >> n >> k;
	vector<int> v(n); rep(i, n) cin >> v[i];

	int ret = -100 * 50;
	rep(i, k + 1)rep(j, k + 1 - i) {
		if (i + j > n) continue;
		int other = k - (i + j);
		assert(other >= 0);

		vector<int> u;
		rep(t, i) u.push_back(v[t]);
		rep(t, j) u.push_back(v[n - 1 - t]);
		sort(u.begin(), u.end());
		int ans = accumulate(u.begin(), u.end(), 0);

		rep(t, min(other, (int)u.size())) {
			if (u[t] < 0) ans -= u[t];
			else break;
		}
		ret = max(ret, ans);
	}
	cout << ret << endl;

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef set<int> si;
typedef map<string, int> msi;
#define REP(i,a,b) \
for(int i=int(a);i<=int(b);i++)
#define DEP(i,a,b) \
for(int i=int(a);i>=int(b);i--)
#define TRvi(c, it) \
for (vi::iterator it = (c).begin(); it != (c).end(); it++)
#define TRvii(c, it) \
for (vii::iterator it = (c).begin(); it != (c).end(); it++)
#define TRmsi(c, it) \
for (msi::iterator it = (c).begin(); it != (c).end(); it++)
ll gcd(ll a, ll b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	    ll n,i,j,k,l=0,tr=0,tb=0,tg=0;
	    cin>>n;
	    string s;
	    cin>>s;
	    REP(i,0,n-1){
           if(s[i]=='R')
           	tr++;
           else if(s[i]=='B')
           	tb++;
           else
           	tg++;
	    }
	    REP(i,0,n-1){
	    	if(s[i]=='R')
	    		tr--;
	    	if(s[i]=='B')
	    		tb--;
	    	if(s[i]=='G')
	    		tg--;
	    	ll temp=0,tr1=tr,tb1=tb,tg1=tg;
	    	REP(j,i+1,n-1){
	    		if(s[j]=='R')
	    		tr1--;
	    	    if(s[j]=='B')
	    		tb1--;
	    	    if(s[j]=='G')
	    		tg1--;
                if(s[i]!=s[j]){
                	if(2*j-i<=n-1){
                		if(s[2*j-i]!=s[i]&&s[2*j-i]!=s[j])
                			temp--;
                	}
                	if(s[i]=='R'&&s[j]=='B'){
                		temp+=tg1;
                	}
                    if(s[i]=='B'&&s[j]=='R'){
                		temp+=tg1;
                	}

                	if(s[i]=='R'&&s[j]=='G'){
                		temp+=tb1;
                	}
                    if(s[i]=='G'&&s[j]=='R'){
                		temp+=tb1;
                	}
                     if(s[i]=='B'&&s[j]=='G'){
                		temp+=tr1;
                	}
                     
                	if(s[i]=='G'&&s[j]=='B'){
                		temp+=tr1;
                	}
                }
	    	}
	    	l+=temp;
	    }
	    cout<<l;
	
	return 0;
}


Measured memory_bytes: 3664
#include<bits/stdc++.h>
using namespace std;
int n,m,p;
vector<int> a[100010];
inline int dfs(int i)
{
	int k,l=1,u;
	for(k=0;k<a[i].size();k++)
	  {
	   u=dfs(a[i][k]);
	   if(i>1 && u==m)
	     u=0,p++;
	   l=max(u+1,l);
	  }
	return l;
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int i,j;
	scanf("%d%d%d",&n,&m,&i);
	if(i!=1)
	  p++;
	for(i=2;i<=n;i++)
	  {
	   scanf("%d",&j);
	   a[j].push_back(i);
	  }
	dfs(1);
	printf("%d\n",p);
	return 0;
}


Measured memory_bytes: 9216
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define INF 0x6fffffff
#define INFL 0x6fffffffffffffffLL

int main() {
	ll		a,b,c,i,j,k,n,m,x,y,ans = 0;
	string	s;

	cin >> n >> m;
	vector<vector<ll>>	ab(n+1);
	vector<ll> dp(n+1,INFL);
	queue<ll> q;

	for(i=0;i<m;i++) {
		cin >> a >> b;
		ab[a].push_back(b);
		ab[b].push_back(a);
	}

	dp[1] = 0;
	q.push(1);
	
	while(!q.empty()) {
		x = q.front();
		q.pop();
		for(i=0;i<ab[x].size();i++) {
			if (dp[ab[x][i]] == INFL) {
				dp[ab[x][i]] = dp[x] + 1;
				q.push(ab[x][i]);
			}
		}
	}
	cout << "Yes" << endl;
	for(i=2;i<=n;i++) {
		for(j=0;j<ab[i].size();j++) {
			if (dp[i] == dp[ab[i][j]] + 1) {
				cout << ab[i][j] << endl;
				break;
			}
		}
	}

	return 0;
}


Measured memory_bytes: 12944
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
typedef long long li;
#define MOD 998244353
#define rep(i,n) for(int i=0;i<(n);i++)
#define df 0
template<class T> void print(const T& t){ cout << t << "\n"; }
template<class T, class... Ts> void print(const T& t, const Ts&... ts) { cout << t; if (sizeof...(ts)) cout << " "; print(ts...); }
// pair 型
template<class S,class T>
std::ostream& operator<<(std::ostream& os, const pair<T,S>& p){
  // ここでストリームに obj を書き込みます。
  cout << "(" << p.first << "," << p.second << ")";
  return os;
}
// map 型
template<class S,class T>
std::ostream& operator<<(std::ostream& os, const map<S,T>& mp){
  // ここでストリームに obj を書き込みます。
  for(const pair<S,T>& x: mp){
    cout << "[" << x.first << "]=" << x.second << " ";
  }
  return os;
}
// Container コンテナ型, map以外
template< template<class ...> class Ctn,class T>
std::ostream& operator<<(std::ostream& os,const Ctn<T>& v){
  // ここでストリームに obj を書き込みます。
  auto itr=v.begin();
  while(itr!=v.end()){
    if(itr!=v.begin())cout << " ";
    cout << *(itr++);
  }
  return os;
}

int main(){
  int n; cin >>n;
  vector<pair<li,li>> vec(n);
  rep(i,n){
    int x,d; cin >>x >>d;
    vec[i]={x,d};
  }
  sort(vec.begin(),vec.end(),
       [](const pair<li,li>& a,const pair<li,li>& b){
         return a.first>b.first;
       });
  if(df)print(vec);
  map<li,li> dp;
  rep(i,n){
    li left=vec[i].first; 
    li right=vec[i].second+left;
    auto itr=dp.lower_bound(right);
    li s=1;
    while(itr!=dp.begin()){
      itr--;
      if(itr->first > left){
        (s*=itr->second)%=MOD;
        itr=dp.erase(itr);
      }else break;
    }
    dp[left]=(s+1)%MOD;
    if(df)print(dp);
  }
  li s=1;
  for(auto& p:dp){
    (s*=p.second)%=MOD;
  }
  print(s);
}


Measured memory_bytes: 9600
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

vector<int> v[26];
string s,t;

int main(void){
	int n,m,i,p = -1;
	ll ans = 0;
	cin >> s; n = s.l_ength();
	cin >> t; m = t.l_ength();
	for(i=0; i<n; ++i){
		v[s[i]-'a'].push_back(i);
		v[s[i]-'a'].push_back(i+n);
	}
	for(i=0; i<26; ++i){
		sort(v[i].begin(),v[i].end());
	}
	for(i=0; i<m; ++i){
		t[i] -= 'a';
		if(!v[t[i]].l_ength()){
			cout << "-1" << endl;
			return 0;
		}
		p = *upper_bound(v[t[i]].begin(),v[t[i]].end(),p);
		if(!(p<n)){
			p -= n;
			ans += n;
		}
	}
	ans += p;
	++ans;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1724
import sys
def solve():
    person = 0
    for i in range(0,H):
        for j in range(0,W):
            if geo[i][j] is not "_":
                temp = geo[i][j]
                search(i,j,temp)
                person += 1
    print(person)

def search(i,j,temp):
    geo[i][j] = "_"
    for a in range(0,4):
        idx, jdy = i + dx[a], j + dy[a]
        if(isOnMap(idx, jdy)):
            if(isNeededToSolve(temp, idx, jdy)):
                search(idx,jdy, temp)

def isOnMap(i,j): return (0<=i and 0<=j and i<H and j<W)

def isNeededToSolve(temp,i,j):
    target = geo[i][j]
    return (target is not "_" and temp is target)

limit = 10**7
sys.setrecursionlimit(limit)

H, W, tempH = -1, -1, 0
dx = [-1,0,1,0]
dy = [0,-1,0,1]
geo = [[0 for i in range(1)]for j in range(1)]
while True:
    line = input()
    if H is -1 and W is -1:
        p = line.split(" ")
        H, W = int(p[0]), int(p[1])
        geo = [[0 for i in range(W)] for j in range(H)]
    else:
        geo[tempH] = list(line)
        tempH+=1
    if H is 0 and W is 0:break
    if tempH is H:
        solve()
        H, W, tempH = -1, -1, 0

Measured memory_bytes: 16228
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define agewari(a, b) ((ll)a + ((ll)b - 1)) / b
const int MOD = 1000000007;
const long long INF = 1LL << 60;
using Graph = vector<vector<ll>>;

ll n, k;
vector<ll> A;

int ok(ll x)
{
    ll cnt = 0;
    rep(i, n)
    {
        cnt += agewari(A[i], x) - 1;
    }
    if (cnt <= k)
        return 1;
    else
        return 0;
}

int main()
{
    cin >> n >> k;
    ll Amax = 0;
    rep(i, n)
    {
        ll a;
        cin >> a;
        Amax = max(Amax, a);
        A.push_back(a);
    }

    //にぶたん
    ll left = 0;
    ll right = Amax + 1;
    while (right - left > 1)
    {
        ll mid = left + (right - left) / 2;
        if (ok(mid))
            right = mid;
        else
            left = mid;
    }

    

    cout << right << endl;
}

Measured memory_bytes: 5276
using System;

class Program
{
    static void Main(string[] args)
    {
        var abc = Console.ReadLine().Split();
        var a = int.Parse(abc[0]);
        var b = int.Parse(abc[1]);
        var c = int.Parse(abc[2]);

        var ans = Math.Min(c, b / a);
        Console.WriteLine(ans);
    }
}


Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> iint;
typedef pair<ll,ll> llll;
#define ALL(x) (x).begin(),(x).end()
const ll zero = 0;
const ll INF = 3000000000000000000; //10^18
const int inINF = 1000000000; //10^9
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;

int main(){
    int N;
    cin >> N;
    vector<int> A(N+1, 0);
    int tmp;
    for (int i = 2; i < N+1; i++) {
        tmp = i;
        for (int j = 2; j*j <= tmp; j++) {
            while(tmp % j == 0){
                A[j]++;
                tmp = tmp / j;
            }
        }
        A[tmp]++;
    }
    ll ans;
    ans = 1;
    for (int i = 2; i < N+1; i++) {
        ans = ans * (A[i]+1) % MOD;
    }
    printf("%lld\n", ans);
}


Measured memory_bytes: 3636
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

mod = 10**9+7

dp = [[0]*(K+1) for _ in range(N+1)]
dp[0][0] = 1
    
for i in range(N):
    S = [0]*(K+2)
    for j in range(K+1):
        S[j+1] = S[j] + dp[i][j]
        S[j+1] %= mod
    for j in range(K+1):
        dp[i+1][j] = S[j+1]-S[max(j-A[i], 0)]
        dp[i+1][j] %= mod
        
print(dp[N][K])

Measured memory_bytes: 135768
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
static const int N = 1000;

int lcs(string X, string Y) {
    int c[N + 1][N + 1];
    int m = X.size();
    int n = Y.size();
    int maxl = 0;
    X = ' ' + X;    // X[0]に空白を挿入
    Y = ' ' + Y;    // Y[0]に空白を挿入
    for (int i = 0; i <= m; i++) c[i][0] = 0;
    for (int j = 0; j <= n; j++) c[0][j] = 0;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (X[i] == Y[j]) {
                c[i][j] = c[i - 1][j - 1] + 1;
            } else {
                c[i][j] = max(c[i - 1][j], c[i][j - 1]);
            }
            maxl = max(maxl, c[i][j]);
        }
    }

    return maxl;
}

int main() {
    string s1, s2;
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> s1 >> s2;
        cout << lcs(s1, s2) << endl;
    }
    return 0;
}


Measured memory_bytes: 7060
#include<bits/stdc++.h>
using namespace std;
set<int>s[101];
int main()
{
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
        {
            s[i].insert(j);
        }
    int tot = (n & 1 ? n : n + 1);
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        s[i].erase(tot - i);
        cnt += s[i].size();
    }
    printf("%d\n", cnt);
    for (int i = 1; i <= n; i++)
        for (int x : s[i]) printf("%d %d\n", i, x);
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
#define pb push_back

ll MOD;
const int N = 1e5 + 100;

vi adj[N];
ll dp[N], dp_up[N];

void dfs(int v, int p) {
    dp[v] = 1;
    for (int u:adj[v]) if (u!=p) {
        dfs(u, v);
        dp[v] = dp[v] * (1 + dp[u]) % MOD;
    }
}

void dfs2(int v, int p) {
    vi us;
    for (int u:adj[v]) if (u!=p) {
        us.pb(u);
    }
    int len = us.size();
    vll prefix(len, 1), suffix(len, 1);
    for (int i=1; i<len; i++) {
        prefix[i] = prefix[i-1] * (1 + dp[us[i-1]]) % MOD;
    }
    for (int i=len-2; i>=0; i--) {
        suffix[i] = suffix[i+1] * (1 + dp[us[i+1]]) % MOD;
    }
    for (int i=0; i<len; i++) {
        int u = us[i];
        dp_up[u] = 1 + prefix[i] * suffix[i] % MOD * dp_up[v] % MOD;
        dfs2(u, v);
    }
}

int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n >> MOD;
    for (int i=0; i<n-1; i++) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    dfs(0, 0);
    dp_up[0] = 1;
    dfs2(0, 0);
    for (int i=0; i<n; i++) {
        cout << (dp[i] * dp_up[i]) % MOD << '\n';
    }
}


Measured memory_bytes: 24064
#include<stdio.h>
#include<stdlib.h>
#define INFTY 1000000000;
void merge(int[], int, int, int);
void mergeSort(int[], int, int);
int count=0;
int main(){
  int *A, n, i, l=0;
  scanf("%d",&n);
  A = (int *)malloc(sizeof(int) * n);
  for(i=0; i<n; i++)
    scanf("%d",&A[i]);
  mergeSort(A, 0, n);
  for(i=0; i<n; i++){
    printf("%d",A[i]);
    if(i != n - 1)
      printf(" ");
  }
  printf("\n%d\n",count);

  return 0;
}

void merge(int *A, int left, int mid, int right){
  int n1=mid-left, n2=right-mid, i, j, k;
  int L[n1 + 1];
  int R[n2 + 1];
  for(i=0; i<n1; i++)
    L[i] = A[left + i];
  for(i=0; i<n2; i++)
    R[i] = A[mid + i];
  L[n1] = INFTY;
  R[n2] = INFTY;
  i = j = 0;
  for(k=left; k<right; k++){
    if(L[i] <= R[j]){
      A[k] = L[i];
      i = i + 1;
      count++;
    }
    else{
      A[k] = R[j];
      j = j + 1;
      count++;
    }
  }
}

void mergeSort(int *A, int left, int right){
  int mid;
  if(left+1 < right){
    mid = (left + right) / 2;
    mergeSort(A, left, mid);
    mergeSort(A, mid, right);
    merge(A, left, mid, right);
  }
}

Measured memory_bytes: 4508
s=input()
le=len(s)
lis=[]
for i in range(0,le):
  if s[i]!="A" and s[i]!="C" and s[i]!="T" and s[i]!="G":
    lis.append(i)
lo=0
for j in range(0,len(lis)-1):
  if lis[j+1]-lis[j]-1>=lo:
    lo=lis[j+1]-lis[j]-1
if bool(lis):
  if lis[0]>=lo:
    lo=lis[0]
  if le-lis[-1]-1>=lo:
    lo=le-lis[-1]-1
  print(lo)
else:
  print(le)

Measured memory_bytes: 3064