akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

int gcd(int a, int b)
{
	if(a < b)
		return gcd(b,a);
	if(b == 0)
		return a;
	if(a%b == 0)
		return b;
	return gcd(a%b,b);
}
int main()
{
	int k;
	cin>>k;
	long ans = 0;
	for(int i = 1; i <= k ; i ++)
	{
		for(int j = 1 ; j <= k ; j ++)
		{
			for(int l =1 ; l <= k ; l++)
			{
				int a = gcd(i,j);
				if(a == 1)
					ans += 1;
				else ans += gcd(a,l);
			}
		}
	}
	cout<<ans<<endl;
}

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

using namespace std;

long long __f(long long a,long long b){
	if(!a||!b) return 0; 
	long long w=(2ll*(b/a)-(b%a==0))*a; 
	return w+__f(b%a,a); 
}

int main(){
	long long n,x; 
	cin>>n>>x;  
	cout<<n+__f(x,n-x)<<endl; 
	return 0; 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
template <class T>
bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

int main() {
    int n, a, b;
    cin >> n >> a >> b;
    vector<int> ans(n);
    rep(i, b) ans[i] = b - i;
    if (a == 1) {
        if (b == n) {
            rep(i, n) cout << n - i << " \n"[i == n - 1];
        } else {
            cout << -1 << endl;
        }
        return 0;
    }

    int k = ((n - b) + a - 2) / (a - 1);
    int x = (n - b) % (a - 1);
    if (x == 0) x = a - 1;
    int y = a - 1 - x;

    if (k > b || k <= 0 || (y > 0 && k - 1 <= 0)) {
        cout << -1 << endl;
        return 0;
    }
    int pos = b;
    int now = b;
    rep(_, x) {
        for (int i = k; i > 0; i--) {
            ans[pos] = now + i;
            pos++;
        }
        now += k;
    }
    rep(_, y) {
        for (int i = k - 1; i > 0; i--) {
            ans[pos] = now + i;
            pos++;
        }
        now += k - 1;
    }

    rep(i, n) cout << ans[i] << " \n"[i == n - 1];
}

Measured memory_bytes: 3328
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, C, K = MAP()
T = [INT() for _ in range(N)]

T.sort()

ans = 1
cnt = 1
t_limit = T[0]+K

for i in range(1, N):
	if cnt == C:  # 次のバスへ
		t_limit = T[i]+K
		cnt = 1
		ans += 1
	elif t_limit >= T[i]:  # 乗れる
		cnt += 1
	else:  # 次のバスへ
		t_limit = T[i]+K
		cnt = 1
		ans += 1
print(ans)


Measured memory_bytes: 9652
#include <cstdio>
#include <algorithm>
#include <cstdint>

int main() {
  int N;
  scanf("%d", &N);

  intmax_t a[2]={2, 1};
  for (int i=0; i<N; ++i) {
    std::swap(a[0]+=a[1], a[1]);
  }

  printf("%jd\n", a[0]);
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
static const int INF (1<<30);

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

  if (a >= 3200) cout << s << endl;
  else cout << "red" << endl;

  return 0;
}


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

int main(){
	int n;
	cin >> n;
	int ans = 3;
	rep(i, n){
		char c;
		cin >> c;
		if(c == 'Y') ans = 4;
	}
	if(ans == 3){
		cout << "Three" << endl;
	}else{
		cout << "Four" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
/*
//#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
*/

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
/*
//#if __cplusplus >= 201103L
#include <array>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
*/
using namespace std;
#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl

#define uni(x) x.erase(unique(all(x)),x.end())
template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;}
template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;}
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) > (b) ? (b) : (a))

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;

#define INF INT_MAX/3
#define MAX_N 1000
#define M_INF 1000000000
int n,m,v,i;
void solve(){
   cin.tie(0);
  ios::sync_with_stdio(false);
  cin>>n>>m;
std::vector<ll> v(n);
rep(i,n) cin>>v[i];
 ll cnt=1;
 ll l=0;
 // if(l<m) cnt++;
 rep(i,n) {
  l+=v[i];
  if(l<=m) cnt++;
}
cout<<cnt<<endl;
}

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


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

using namespace std;
using ll = long long;

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

    int a;
    ll b, n;
    cin >> a >> b >> n;

    printf("%lld\n", min(a * (b - 1) / b, a * n / b));

    return 0;
}

Measured memory_bytes: 3700
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, j, n) for (ll i = j; i < n; i++)
#define all(x) (x).begin(),(x).end()
#define INF (1000000000)
#define MOD (1000000007)
#define MAX (500000)
#define pii pair<int, int>

/////////////////////////////////////////////////////////

class XY{
public:
  ll x, y;
  XY() {x = y = 0;}
  XY(ll u, ll v) {x = u; y = v;}
};

class e{
public:
  ll a, b;
  e() {a = b = -1;}
  e(ll u, ll v) {a = u; b = v;}
};

template<typename T1, typename T2>
void chmin(T1 &a, T2 b) {if(a > b) a = b;}
template<typename T1, typename T2>
void chmax(T1 &a, T2 b) {if(a < b) a = b;}

template<typename T1, typename T2>
ll mypow(T1 a, T2 n){
  if(n == 0) return 1;
  if(n == 1) return a;
  if(n % 2) return a * mypow(a, n - 1);
  ll tmp = mypow(a, n / 2);
  return tmp * tmp;
}

template<typename T>
int BS(vector<T> &V, int left, int right, T key){
  int mid = (left + right) / 2;
  if(V[mid] <= key) left = mid;
  else right = mid;
  if(right - mid == 1) return left;
  else return BS(V, left, right, key);
}

ll comb(ll n, ll r){
	ll res = 1;
  rep(i, 0, r){
    res *= n - i;
    res /= i + 1;
  }
  return res;
}

template<typename T>
T euclid(T a, T b){
  if(b == 0) return a;
  else return euclid(b, a % b);
}

ll fact[MAX], fact_inv[MAX];

ll pow_mod(ll a, ll b){
	ll res = 1;
	while(b > 0){
		if(b & 1) res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return res;
}

void prepare_comb_mod(ll n){
	fact[0] = 1;
	for(ll i = 0; i < n; i++) fact[i+1] = fact[i] * (i + 1) % MOD;
	fact_inv[n] = pow_mod(fact[n], MOD - 2);
	for(ll i = n - 1; i >= 0; i--) fact_inv[i] = fact_inv[i + 1] * (i + 1) % MOD;
}

ll comb_mod(ll n, ll r){
	return (fact[n] * fact_inv[r]) % MOD * fact_inv[n - r] % MOD;
}

/////////////////////////////////////////////////////////

void Main() {
  string S; cin >> S;
  bool ok1 = false, ok2 = false;
  rep(i, 0, S.size()){
    if(!ok1){
      if(S[i] == 'C') ok1 = true;
    }else{
      if(S[i] == 'F') ok2 = true;
    }
  }
  if(ok2) cout << "Yes" << endl;
  else cout << "No" << endl;
}

/////////////////////////////////////////////////////////

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << std::fixed << std::setprecision(15);

  Main();
}


Measured memory_bytes: 256
from scipy.sparse import*
i=lambda:tuple(map(int,input().split()))
f=csgraph.dijkstra
n,m,l=i()
d=eval('[0]*-~n,'*-~n)
while m:a,b,c=i();d[a][b]=c;m-=1
d=f(f(d,0)<=l)
d[d>n]=0
for _ in'_'*i()[0]:print(int(d[i()])-1)

Measured memory_bytes: 19640
#include <iostream>

using namespace std;

int main(void){
     char field[8][8];
     char tmp;
     int i,j;
	 while(1){
	   for(i=0;i<8;i++){
		 for(j=0;j<8;j++){
		   cin >> field[i][j];
		   //cout << field[i][j];
		 }
		 //cout << endl;
	   }
	   
	   //»ê¼êÌ`ÉÂ¢Ä»Ê
	   //Ü¸¶ãÌ}XðT·
	   for(i=0;i<8;i++){
		 for(j=0;j<8;j++){
		   if(field[i][j] == '1') goto NEXT;
		 }
	   }
	 NEXT:
	   //cout << i << "    " << j << endl;

     
	   if(j+3 <= 7 && field[i][j+1] == '1' && field[i][j+2] == '1' && field[i][j+3] == '1'){
		 //¡êñ
		 cout << "C" << endl;
	   }else if(i+3 <= 7 && field[i+1][j]  == '1' && field[i+2][j] == '1' && field[i+3][j] == '1'){
		 //cêñ
		 cout << "B" << endl;
	   }else if(j+1 <= 7 && i+1 <= 7 && field[i][j+1] == '1' && field[i+1][j] == '1' && field[i+1][j+1] == '1'){
		 //³û`
		 cout << "A" << endl;
	   }else if(i+2 <= 7 && j+1 <= 7 && field[i+1][j] == '1' && field[i+1][j+1]  == '1' && field[i+2][j+1] == '1'){
		 //1 0
		 //1 1
		 //0 1
		 cout << "F" << endl;
	   }else if(j-1 >= 0 && j+1 <= 7 && i+1 <= 7 && field[i][j+1] == '1' && field[i+1][j] == '1' && field[i+1][j-1] == '1'){
		 //0 1 1
		 //1 1 0
		 cout << "G" << endl;
	   }else if(j+2 <= 7 && i+1 <= 7 && field[i][j+1] == '1' && field[i+1][j+1]  == '1' && field[i+1][j+2] == '1'){
		 //1 1 0
		 //0 1 1
		 cout << "E" << endl;
	   }else{
		 cout << "D" << endl;
	   }
	   cin.ignore();
	   cin.ignore();
	   if(cin.eof()) return 0;
	 }
	 return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;

#define REP(i,n) for(int (i)=0; (i)<(n); (i)++)
#define For(i,a,b) for(int (i)=(a); (i)<(b); (i)++)

int main() {
    vector<int> v(5);
    char ch;
    while(cin>>v[0]>>ch>>v[1]>>ch>>v[2]>>ch>>v[3]>>ch>>v[4]) {
        sort(v.begin(), v.end());
        int n = 0;
        REP(i,4) {
            For(j,i+1,5) {
                if (v[i] == v[j]) n++;
            }
        }
        
        switch(n) {
            case 1:
                cout << "one pair" << endl;
                break;
            case 2:
                cout << "two pair" << endl;
                break;
            case 3:
                cout << "three card" << endl;
                break;
            case 4:
                cout << "full house" << endl;
                break;
            case 6:
                cout << "four card" << endl;
                break;
            default:
                if (v[0] == v[4]-4 || (v[0] == 1 && v[1] == 10)) {
                    cout << "straight" << endl;
                }else {
                    cout << "null" << endl;
                }
                break;
        }
    }
    return 0;
}

Measured memory_bytes: 1204
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <bitset>
#include <string>
using namespace std;
 
#define rep(i,n) for(int i=0; i<n; i++)
#define repa(i,s,e) for(int i=s; i<=e; i++)
#define repd(i,s,e) for(int i=s; i>=e; i--)
#define PB(a) push_back(a)
#define MP(i,s) make_pair(i,s)
 
typedef long long ll;

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

const int field[5][5] = {
	{0, 0, 1, 0, 0}, 
	{0, 1, 1, 1, 0},
	{1, 1, 1, 1, 1},
	{0, 1, 1, 1, 0},
	{0, 0, 1, 0, 0}, 
};

const int ans[5][5] = {
	{0, 0, 0, 0, 0},
	{0, 1, 2, 3, 0},
	{4, 5, 6, 7, 8},
	{0, 9, 10, 11, 0},
	{0, 0, 0, 0, 0}
};

const int px[13] = {2, 1, 2, 3, 0, 1, 2, 3, 4, 1, 2, 3, 2};
const int py[13] = {0, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 4};

int P[5][5];
map<ll,int> used;
map<ll,int> H;

ll hash_val() {
	ll h = 0;
	rep(i,13) {
		h *= 13;
		h += P[py[i]][px[i]];
	}
	return h;
}

void make_ans(int m, int d) {
	ll h = hash_val();
	map<ll,int>::iterator it = H.find(h);
	
	if(it == H.end()) {
		H.insert(MP(h,m));
	} else if((*it).second > m) {
		(*it).second = m;
	} else {
		return;
	}

	if(m == d) return;


	rep(i,13) {
		int x = px[i];
		int y = py[i];
		if(P[y][x] == 0) {
			rep(k,4) {
				int xx = x + dx[k];
				int yy = y + dy[k];
				if(xx>=0 && yy>=0 && xx<5 && yy<5 && field[yy][xx] == 1 && P[yy][xx] != 0) {
					swap(P[y][x], P[yy][xx]);
					make_ans(m+1, d);
					swap(P[y][x], P[yy][xx]);
				}
			}
		}
	}
}

int dfs(int m, int d) {
	map<ll,int>::iterator it;
	ll h = hash_val();

	it = H.find(h);
	if(it != H.end()) return m + (*it).second;

	if(m == d) return -1;
	
	it = used.find(h);
	if(it == used.end()) {
		used.insert(MP(h,m));
	} else if((*it).second > m) {
		(*it).second = m;
	} else {
		return -1;
	}

	rep(i,13) {
		int x = px[i];
		int y = py[i];
		if(P[y][x] == 0) {
			rep(k,4) {
				int xx = x + dx[k];
				int yy = y + dy[k];
				if(xx>=0 && yy>=0 && xx<5 && yy<5 && field[yy][xx] == 1 && P[yy][xx] != 0) {
					swap(P[y][x], P[yy][xx]);
					int a = dfs(m+1, d);
					if(a >= 0) return a;
					swap(P[y][x], P[yy][xx]);
				}
			}
		}
	}
	return -1;
}

void solve() {
	repa(d,0,10) {
		used.clear();
		int a = dfs(0, d);
		if(a >= 0) {
			printf("%d\n", a);
			return;
		}
	}
	printf("NA\n");
}

int main() {
	memcpy(P, ans, sizeof(P));
	make_ans(0, 10);
	for(;;) {
		rep(i,13) {
			scanf("%d", &P[py[i]][px[i]]);
			if(P[py[i]][px[i]] < 0) return 0;
		}
		solve();
	}
}

Measured memory_bytes: 2444
// Package main provides ...
package main

import (
	"fmt"
	"math"
)

func main() {
	var N int
	var m int

	fmt.Scan(&N)

	m = N - 1
	for i := 0; float64(i) <= math.Sqrt(float64(N)); i++ {
		if float64(N)/float64(1+i) - math.Trunc(float64(N)/float64(1+i)) == 0 {
			if i + (N/(1+i)-1) < m {
				m = i + (N/(1+i)-1)
			}
		}
	}
	fmt.Println(m)
}



Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <sstream>
using namespace std;

int main(){
    string str;
    int sum = 0;
    
    while(getline(cin,str)){
        for(int i = 0 ; i < str.size() ; i++){
            if('0' <= str[i] && str[i] <= '9') continue;
            else str[i] = ' ';
        }
        int num;
        stringstream s;
        s << str;
        while(s >> num){
            sum += num;
        }
    }
    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 1224
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
  	cin>>s;
  	int n,half,count=0;
  	n=s.size();
  	if(n%2==1){
      	half=(n-1)/2;
    	for(int i=0;i<half;i++){
        	if(s.at(i)!=s.at((n-1)-i)){
            	count++;
            }
        }
    }
  	else{
    	half=n/2;
      	for(int i=0;i<half;i++){
        	if(s.at(i)!=s.at((n-1)-i)){
            	count++;
            }
        }
    }
  	cout<<count<<endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define all(a)a.begin(),a.end()
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int mod= int(1e9)+7;
//const int mod=998244353;
using P = pair<int,int>;
using Pl= pair<ll,ll>;
using ld=long double;
using V=vector<int>;
using Vl=vector<ll>;
using VV=vector<vector<int>>;
using VVl=vector<vector<ll>>;

int main(){
    string s;cin >>s;
    if(s.back()=='s')s+="es";
    else s+='s';
    cout <<s<<endl;
}


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

#define _GLIBCXX_DEBUG
#define all(v) (v).begin(),(v).end()

using ll=long long;
using pii=pair<int, int>;
using vi=vector<int>;
using vii=vector<vector<int>>;

const ll LINF=1LL<<60;
const int INF=1<<29;
const ll MOD=1e9+7;



int main(){
    int n, m; cin >> n >> m;
    vi a(n), b(n);
    for(int i=0; i<n; i++){
        cin >> a[i] >> b[i];
    }

    int low=0, high=1e9+5;
    while(high-low > 1){
        int mid=low+(high-low)/2;
        ll sum=0;
        vector<priority_queue<int, vi, less<int>>> pque(m);
        priority_queue<int, vi, less<int>> award;
        for(int i=0; i<n; i++){
            if(a[i] > m) continue;
            pque[m-a[i]].push(b[i]);
        }
        for(int i=m-1; i>=0; i--){
            while(!pque[i].empty()){
                award.push(pque[i].top());
                pque[i].pop();
            }
            if(award.empty()) continue;
            sum+=award.top();
            award.pop();
        }
        if(sum >= mid) low=mid;
        else high=mid;
    }
    cout << low << endl;
    return 0;
}

Measured memory_bytes: 9996
#include<bits/stdc++.h>
using namespace std;
const int offset=100000;
int n,a[100005],s[1000050],bit[1000050];
int lowb(int x)
{
	return x&(-x);
}
void add(int x)
{
	while(x<=2*offset)
	{
		bit[x]++;
		x+=lowb(x);
	}
}
long long cal(int x)
{
	long long ans=0;
	while(x>=1)
	{
		ans+=bit[x];
		x-=lowb(x);
	}
	return ans;
}
bool check(int x)
{
	memset(bit,0,sizeof(bit));
	for(int i=1;i<=n;i++)
		s[i]=s[i-1]+(a[i]>=x?1:-1);
	long long sum=0;
	for(int i=0;i<=n;i++)
	{
		sum+=cal(s[i]+offset);
		add(s[i]+offset);
	}
	return sum>=1ll*n*(n+1)/4;
}
int main()
{
	cin>>n;
	int l=0,r=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		r=max(r,a[i]);
	}
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(check(mid)) l=mid+1;
		else r=mid-1;
	}
	cout<<r<<endl;
	return 0;
}


Measured memory_bytes: 8448
#include <bits/stdc++.h>
#define INF 1000000007
#define rep(i, N) for(ll i = 0; i < N; i++)
#define rep2(i, j, k) for(ll i = j; i < k; i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define print(x) cout << x << "\n"
#define print2(x, y) cout << x << " " << y << "\n"
#define printv(vec) rep(lp, vec.size()) cout << vec[lp] << " "; print(""); 
#define ALL(v) v.begin(), v.end()
#define SUM(v) accumulate(ALL(v), 0)
#define MAX(v) *max_element(ALL(v))
#define MIN(v) *min_element(ALL(v))
#define SORT(v) sort(ALL(v))
#define REV(v) reverse(ALL(v))
typedef long long ll;
using namespace std;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vs = vector<string>;

const int mod = 1000000007;
class mint {
public:
    ll x;
    mint(ll x = 0) : x((x % mod + mod) % mod) {}
    mint operator-() const { 
      return mint(-x);
    }
    mint& operator+=(const mint& a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint& a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const  mint& a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint& a) const {
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint& a) const {
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint& a) const {
        mint res(*this);
        return res *= a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }
    mint inv() const {
        return pow(mod - 2);
    }
    mint& operator/=(const mint& a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint& a) const {
        mint res(*this);
        return res /= a;
    }
    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.x;
        return os;
    }
};

ll modpow(ll a, ll n){
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

void Main(){

	string s, t;
	cin >> s >> t;
	
	vvl v(26, vl());
	
	ll lens = s.size();
	ll lent = t.size();
	rep(i, lens) v[s[i] - 'a'].push_back(i);
	
	ll ans = 0;
	ll cnt = -1;
	
	rep(i, lent){
		if(v[t[i] - 'a'].size() == 0){
			print(-1);
			return;
		}
	}
	
	rep(i, lent){

		auto itr = upper_bound(ALL(v[t[i] - 'a']), cnt);
		if(itr == v[t[i] - 'a'].end()){
			ans += lens;
			cnt = v[t[i] - 'a'][0];
		}
		else cnt = *itr;
		//print2(ans, cnt);
	}
	
	ans += (cnt + 1);
	print(ans);
	
}

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





Measured memory_bytes: 4600
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000000


int main(){
	
	long long N,A,B;
	cin>>N>>A>>B;
	
	if(A>B){
		cout<<0<<endl;
		return 0;
	}
	
	if(N==1){
		if(A==B)cout<<1<<endl;
		else cout<<0<<endl;
	}
	else{
		long long mini = A+B;
		long long maxi = A+B;
		N-=2;
		mini += A*N;
		maxi += B*N;
		
		cout<<maxi-mini+1<<endl;
	}
		
	
	return 0;
}

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

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

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


std::string to_soroban(const int &n, const int &level = -1) {
	if (level == 5) {
		return "";
	}
	else if (level == -1) {
		auto rest = to_soroban(n, level + 1);
		std::string upper = "\n";
		std::string lower = "\n";
		int copy = n;
		for (auto i = 0; i < 5; ++i) {
			if (copy % 10 > 4) {
				upper = " " + upper;
				lower = "*" + lower;
			}
			else {
				upper = "*" + upper;
				lower = " " + lower;
			}
			copy /= 10;
		}
		return upper + lower + "=====\n" + rest;
	}
	else {
		auto rest = to_soroban(n, level + 1);
		std::string res = "\n";
		int copy = n;
		for (auto i = 0; i < 5; ++i) {
			if (copy % 5 == level) {
				res = " " + res;
			}
			else {
				res = "*" + res;
			}
			copy /= 10;
		}
		return res + rest;
	}
}
int main() {
	int j;
	std::cin >> j;
	std::cout << to_soroban(j);
	for (int i; std::cin >> i;) {
		std::cout << '\n' << to_soroban(i);
	}
	return 0;
}

Measured memory_bytes: 2952
#include "bits/stdc++.h" 
using namespace std;
#define rep(i,a,n) for(ll i=a;i<n;i++)
#define rerep(i,a,n) for(ll i=n;i>=a;i--)
#define elif else if
#define all(s) s.begin(),s.end()
typedef long long ll;
int gcd(int a,int b){
    if(a<b)swap(a,b);
    if(a%b==0)return b;
    else return gcd(b,a%b);
}
int main(){
    double ans=3.14159265358979*2;
    ll r;
    cin>>r;
    ans*=r;
    cout<<ans<<endl;
}

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

using namespace std;
#define int long long
#define pb push_back
#define fio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
template<class L,class R> ostream& operator<<(ostream& cout,pair<L, R> P)
{return cout<<'('<<P.first<<','<< P.second<<')';}
template<class T> ostream& operator<<(ostream& cout,vector<T> V)
{cout<<"[ ";for(auto v:V)cout<<v<<' ';return cout<<']';}
#define show(x) cout<<#x<<" : "<<x<<'\n';


signed main(){
	fio;
	int t=1;
	// cin>>t;
	while(t--){
		int n, k;
		cin>>n>>k;
		set<int> s;
		for(int i=0; i<k; i++){
			int d;
			cin>>d;
			for(int i=0; i<d; i++){
				int temp;
				cin>>temp;
				s.insert(temp);
			}
		}

		cout<<n- s.size()<<"\n";
	}
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

ll inf = 1000000000000000000;

int main() {
  ll n;
  cin >> n;
  vl a(n);
  rep(i, n) cin >> a[i];
  ll ans = 1;
  rep(i, n) if(a[i] == 0) {
    cout << 0 << endl;
    return 0;
  }
  rep(i, n) {
    if(a[i] > inf / ans || a[i] * ans > inf) {
      ans = -1;
      break;
    }
    ans *= a[i];
  }
  if(ans > inf) ans = -1;
  cout << ans << endl;
}

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

int main()
{
    int a, b;
    cin >> a >> b;
    int r = 0;
    for(int i = a; i <= b; ++i) {
        int s = i % 10,
            t = i / 10000 %10,
            u = i / 10 % 10,
            v = i / 1000 % 10;
            if(s == t && u == v) ++r;
    }
    cout << r << endl;
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;

namespace DSL1_A
{
    class Program
    {
        static void Main(string[] args)
        {
            var t = scan;
            var n = t[0];
            var q = t[1];

            var U = new UnionFind(n);

            for (int i = 0; i < q; i++)
            {
                var k = scan;
                if (k[0] == 0)
                {
                    U.Unite(k[1], k[2]);
                }
                if (k[0] == 1)
                {
                    Console.WriteLine(U.Same(k[1], k[2]) ? 1 : 0);
                }
            }

        }
        static int[] scan { get { return Array.ConvertAll(Console.ReadLine().Split(), int.Parse); } }
    }
    public class UnionFind
    {
        int[] rank;
        int[] p;
        public UnionFind(int size)
        {
            rank = new int[size];
            p = new int[size];
            for (int i = 0; i < size; i++)
            {
                rank[i] = 0;
                p[i] = i;
            }
        }
        public void Unite(int x, int y)
        {
            x = FindSet(x);
            y = FindSet(y);
            if (rank[x] > rank[y]) p[y] = x;
            if (rank[x] < rank[y]) p[x] = y;
            if (rank[x] == rank[y])
            {
                p[x] = y;
                rank[y]++;
            }
        }
        public bool Same(int x, int y)
        {
            return FindSet(x) == FindSet(y);
        }
        public int FindSet(int x)
        {
            var H = new HashSet<int>();
            while (p[x] != x)
            {
                H.Add(x);
                x = p[x];
            }
            foreach (var h in H)
            {
                p[h] = x;
            }
            return x;
        }
    }
}

Measured memory_bytes: 10388
#include<bits/stdc++.h>
using namespace std;
int miner,maxer;
map<string,int>has;
vector<string>s;
string q;
long long ans;
int main(){
	ios::sync_with_stdio(0);
//	freopen("p.in","r",stdin);
//	freopen("p.out","w",stdout);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>q;
		string az(10,'0');
		int cnt=0;
		for(int j=0;j<26;j++){
			char c='a'+j;
			for(int k=0;k<10;k++)
			if(q[k]==c){az[cnt]=c;cnt++;}
		}
		has[az]++;
		if(has[az]==1)s.push_back(az);
	}
	for(int i=0;i<s.size();i++){
		string az=s[i];
      long long zl=has[az];
		ans+=zl*(zl-1)/2;
	}
	cout<<ans;
	return 0;
}

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

long long n, k, w[105], v[105], dp[105][100005], best;

int main(){
	cin>>n>>k;
	for(int i=1; i<=n; i++){
		cin>>w[i]>>v[i];
	}
	
	for(int i=1; i<=n; i++){
		for(int j=1; j<=k; j++){
			best=dp[i-1][j];
			if(j>=w[i])best=max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
			dp[i][j]=best;
		}
		//cout<<dp[i][k]<<endl;
	}
	cout<<dp[n][k]<<endl;
	//cout<<dp[2][3]<<endl;
}


Measured memory_bytes: 79360
#include <bits/stdc++.h>
#define bug1(x) cout<<#x<<" = "<<x<<endl
#define bug2(x,y) cout<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<endl
#define bug3(x,y,z) cout<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<" "<<#z<<" = "<<z<<endl
#define bug4(x,y,z,m) cout<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<" "<<#z<<" = "<<z<<" "<<#m<<" = "<<m<<endl

using namespace std;

class Debugger {
public:
	template<typename T>
	void printVector(vector<T> const &vec, bool printSize=true){
		if(printSize){
			cout << vec.size() << endl;
		}
		for(auto &elem : vec){
			cout << elem << " ";
		}
		cout << endl;
	}

	template<typename T>
	void printMatrix(vector<vector<T>> const &matrix){
		cout << matrix.size()<< " ";
		if(!matrix.empty()){
			cout << matrix[0].size();
		}
		cout << endl; 
		for(auto &vec : matrix){
			printVector(vec, false);
		}
		cout << endl;
	}
};

const int maxN = 200000 + 5;
const double PI = acos(-1);
#define ll long long

class TaskC {
private:
	Debugger debugger;

public:
	void solveOne(int it){
		int lim;
		cin >> lim;
		for(int n = 1; n <= lim; n++){
			int ans = 0;
			for(int x = 1; x*x <= n; x++){
				for(int y = 1; x*x + y*y + x*y <= n; y++){
					for(int z = 1; x*x + y*y + z*z + x*y + x*z + y*z <= n; z++){
						if(x*x + y*y + z*z + x*y + x*z + y*z == n){
							ans++;
						}
					}
				}
			}
			cout << ans << endl;
			
		}
	}

	void solve(){
		int tc = 1;
		for(int it = 1; it <= tc; it++){
			solveOne(it);
		}
	}
};


int main(){
	ios_base::sync_with_stdio(false);
	TaskC solver;
	solver.solve();
	return 0;
}


Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
int dp[100][100];
int main() {
    int h, w, ans = 0, x;
    scanf("%d%d", &h, &w);
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            scanf("%d", &dp[i][j]);
        }
    }
    for (int k = 0; k < 10; k++) {
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
            }
        }
    }
    for (int i = 0; i < h * w; i++) {
        scanf("%d", &x);
        if (x >= 0) ans += dp[x][1];
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

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

    int n = scanner.nextInt();
    int min = 1000000;
    int max = -1000000;
    long sum = 0;

    for (int i = 0; i < n; i++) {
      int x = scanner.nextInt();
      if (x < min) min = x;
      if (max < x) max = x;
      sum += x;
    }

    System.out.println(min + " " + max + " " + sum);
    scanner.close();
  }
}

Measured memory_bytes: 31888
// https://atcoder.jp/contests/abc146/tasks/abc146_b
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	input = input.split("\n");
	var inputN = parseInt(input[0]);
	var inputS = input[1].split("");

	// アルファベット
	var alphabets = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'];

	var inputSLength = inputS.length;
	var inputNum = [];

	for ( var i=0;i < inputSLength;i++){
		inputNum[i] = 0;
		for (var j=0;j < 26;j++){
			if (inputS[i] === alphabets[j]){
				inputNum[i] = j;
				break;
			}
		}
	}
	var inputNPer = inputN % 26;
	var result = '';

	for(var i=0;i < inputSLength;i++){
		var temp = inputNum[i] + inputNPer
		// console.log(temp);
		if (temp > 25) temp = temp % 26;
		result += alphabets[temp];
	}
	console.log(result);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 7756
#include <iostream>
using namespace std;
using ll = long long;

int main() {
    int n; cin >> n;
    ll A[n + 2];
    A[0] = 2, A[1] = 1; 

    for (int i = 0; i <= n - 2; i++) {
        A[i + 2] = A[i + 1] + A[i];
    }
    cout << A[n] << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <stdio.h>

using namespace std;

int n;
double x1, x2, x3, x4, y1, y2, y3, y4, slope1, slope2;

double abs(double s) {
    return s < 0 ? -s : s;
}

int main(void) {
    cin >> n;
    while(n--) {
        cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
        slope1 = (y1 - y2) / (x1 - x2);
        slope2 = (y3 - y4) / (x3 - x4);

        if(slope1 == slope2) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 0
import qualified Data.ByteString.Char8 as BS
import Data.Maybe

readInt = fromIntegral . fst . fromJust . BS.readInteger
readIntList = map readInt . BS.words

getInt = readInt <$> BS.getLine
getIntList = readIntList <$> BS.getLine

main = do
  [h1, m1, h2, m2, k] <- getIntList
  print $ h2 * 60 + m2 - (h1 * 60 + m1 + k)


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
int ctoi(char c) {
  if (c >= '0' && c <= '9') {
    return c - '0';
  }
  return 0;
}
ll factorial(ll n) {
  if (n == 1) {
    return 1;
  }
  ll ans = factorial(n-1);
  return ans*n;
}
ll gcd(ll a, ll b) {
  if (a < b) {
    ll tmp = a;
    a = b;
    b = tmp;
  }
  ll r = a%b;
  while(r != 0) {
    a = b;
    b = r;
    r = a%b;
  }
  return b;
}
ll lcm(ll a, ll b) {
  return (a/gcd(a, b))*b;
}

int main() {
  ll n;
  cin >> n;
  vector <ll> v(n);
  rep(i, n) {
    cin >> v.at(i);
    if (i < n-1) {
      cout << v.at(i) << ' ';
    } else {
      cout << v.at(i) << endl;
    }
  }
  for (ll i = 1; i < n; i++) {
    ll a = v.at(i);
    ll j = i-1;
    while (j>=0 && v.at(j)>a) {
      v.at(j+1) = v.at(j);
      j--;
    }
    v.at(j+1) = a;
    rep(i, n) {
      if (i < n-1) {
        cout << v.at(i) << ' ';
      } else {
        cout << v.at(i) << endl;
      }
    }
  }
}


Measured memory_bytes: 3092
#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>;

struct UnionFind{
    vector<int> parent;
    vector<int> rank;
    vector<int> member;
    UnionFind(int n):rank(n+1,0),parent(n+1),member(n+1){
        rep(i,n+1) parent[i]=i;
        rep(i,n+1) member[i]=1;
    }

    int find(int x){
        if (parent[x] == x) return x;
        else return parent[x] = find(parent[x]);
    }

    void unite(int x, int y){
        x = find(x);
        y = find(y);
        if (x==y) return;


        else if(rank[x]<rank[y]) {
            member[y]+=member[x];
            member[x]=member[y];
            parent[x]=y;
        }
        else{
            member[x]+=member[y];
            member[y]=member[x];
            parent[y]=x;
            if (rank[x]==rank[y]){
                rank[x]+=1;
            }
        }
    }
};


int main(){
    int n,m;
    cin >> n >> m;
    vector<int> a(m);
    vector<int> b(m);

    rep(i,m){
        cin >> a[i] >> b[i];   
    }
    UnionFind uf(n);
    
    vector<ll> res;
    res.push_back(ll(n)*ll(n-1)/ll(2));

    rep(zzz,m){
        int i = m-1-zzz;
        int ma,mb;
        ma = uf.member[uf.find(a[i])];
        mb = uf.member[uf.find(b[i])];
        //cout << "before " << "a: " << ma << " b: " << mb << endl; 
        uf.unite(a[i],b[i]);
        //cout << "after " << "a: " <<  uf.member[uf.find(a[i])] << " b: " << uf.member[uf.find(b[i])]  << endl; 

        ll temp;
        
        temp = res[res.size()-1]-ll(ma)*ll(uf.member[uf.find(a[i])]-ma);
        //cout << "temp " << temp << endl;
        res.push_back(temp);
    }

    rep(i,res.size()-1){
        cout << res[res.size()-2-i]<<endl; 
    }



}

Measured memory_bytes: 4212
import collections
n = int(raw_input())

adj = collections.defaultdict(list)

for _ in range(n - 1):
	u, v, w = map(int, raw_input().split(' '))
	adj[u].append((v,w))
	adj[v].append((u,w))


q = collections.deque([(1,0)])
h = { 1:0 }
while(q):
	u,c = q.popleft()
	for v,w in adj[u]:
		if v not in h:
			h[v] = (1- c) if (w % 2) else c
			q.append((v,h[v]))

for node in range(1, n + 1): 
	print h[node]

Measured memory_bytes: 74780
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int H, N, ans = 0;
  cin >> H >> N;
  for (int i = 0; i < N; i++) {
    int a;
    cin >> a;
    ans += a;
  }
  if (ans >= H) {
    cout << "Yes"<< endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
//abc151
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define mod 1000000007
#define FS fixed<<setprecision(15)
using namespace std;
typedef long long ll;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
using P=pair<ll,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

const ll INF=1e18;

ll mod_pow(ll x,ll n,ll m){
    if(n==0) return 1;
    ll res=mod_pow(x*x%m,n/2,m);
    if(n&1) res=res*x%m;
    return res;
}

ll c[100005];

int main(){
    ll n,k;
    cin>>n>>k;
    V<ll> a(n);
    cinf(n,a);
    if(k==1) cout<<0<<endl;
    else{
        sort(all(a));
        c[k-1]=1;
        for(ll i=k;i<=n;i++){
            c[i]=(c[i-1]*i)%mod;
            c[i]=(c[i]*mod_pow(i-k+1,mod-2,mod))%mod;
        }
        //for(ll i=k;i<=n-1;i++)
        ll cnt_ma=0,cnt_mi=0,ans;
        for(ll i=n-k;i>=0;i--) cnt_mi=(cnt_mi+(a[i]*c[n-i-1])%mod)%mod;
        for(ll i=k-1;i<n;i++) cnt_ma=(cnt_ma+(a[i]*c[i])%mod)%mod;
        ans=(cnt_ma-cnt_mi)%mod;
        while(ans<0) ans+=mod;
        /*for(ll i=k-1;i<n;i++) cout<<c[i]<<' ';
        cout<<endl;*/
        cout<<ans<<endl;
    }
}

Measured memory_bytes: 1408
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>

#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define EACH(i, c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

//#define LOCAL 0
//#ifdef LOCAL
//#define DEBUG(s) cout << (s) << endl
//#define dump(x)  cerr << #x << " = " << (x) << endl
//#define BR cout << endl;
//#else
//#define DEBUG(s) do{}while(0)
//#define dump(x) do{}while(0)
//#define BR
//#endif


//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 20)
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x)  cerr << #x << " = " << (x) << endl

//ここから編集する


int main() {
    int W, H;
    cin >> W >> H;
    vector<ll> p(W), q(H), ruip;
    rep(i, 0, W) {
        cin >> p[i];
    }
    rep(i, 0, H) {
        cin >> q[i];
    }

    sort(all(p));
    ruip.push_back(0);
    rep(i, 0, W) {
        ruip.push_back(*(ruip.end() - 1) + p[i]);
    }

    ll ans = 1ll * ruip[W];
    rep(i, 0, H) {
        ans += 1ll * q[i];
    }


    rep(i, 0, H) {
        ans += 1ll * (p.end() - upper_bound(all(p), q[i])) * q[i];
        ans += 1ll * ruip[upper_bound(all(p), q[i]) - p.begin()];
    }

    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 2936
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <cmath>
#include <queue>
#include <map>
using namespace std;

int main(){
    int n,x,y ;
    cin >> n >> x >> y ;
    vector<int> ans(n) ;
    vector<vector<int> > list(n,vector<int>(0)) ;
    for (size_t i = 0; i < n; i++)
    {
        if (i > 0)
        {
            list.at(i).push_back(i-1) ;
        }
        if (i < n-1)
        {
            list.at(i).push_back(i+1) ;
        }
        
    }
    list.at(x-1).push_back(y-1) ;
    list.at(y-1).push_back(x-1) ;
    queue<int> wait ;
    for (size_t i = 0; i < n-1; i++)
    {
        vector<int> dist(n,-1) ;
        dist.at(i) = 0 ;
        int now = i ;
        for (size_t j = 0; j < list.at(i).size(); j++)
        {
            wait.push(list.at(i).at(j)) ;
            dist.at(list.at(i).at(j)) = dist.at(now) + 1 ;
        }
        while (wait.empty() == 0)
        {
            int now = wait.front() ;
            wait.pop() ;
            for (size_t j = 0; j < list.at(now).size(); j++)
            {
                int jj = list.at(now).at(j) ;
                if (dist.at(jj) == -1)
                {
                    wait.push(jj) ;
                    dist.at(jj) = dist.at(now) + 1 ;
                }
                
            }
            
        }
        for (size_t j = i+1; j < n; j++)
        {
            ans.at(dist.at(j)) ++ ;
        }
        
    }
    for (size_t i = 1; i < n; i++)
    {
        cout << ans.at(i) << endl ;
    }
    
}

Measured memory_bytes: 384
n,m,x,y = [int(_) for _ in input().split()]
xList = sorted([int(_) for _ in input().split()])
yList = sorted([int(_) for _ in input().split()])

if xList[-1] < yList[0] and x < yList[0] <= y:
  print("No War")
else:
  print("War")

Measured memory_bytes: 3060
// Author: πα

#include <bits/stdc++.h>
using namespace std;

#define FastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define long int64_t

const int N = 1e5 + 105;
const int INF = 1000000007;
int a[N], b[N];

int main()
{
    FastIO;
    int n, i, j, k;
    cin >> n >> k;
    for(i = 0; i < n; ++i)
        cin >> a[i], b[i] = INF;
    b[0] = 0;
    for(i = 0; i < n; ++i)
        for(j = i; j <= i+k; ++j)
            b[j] = min(b[j], b[i] + abs(a[i]-a[j]));
    cout << b[n-1];
    return 0;
}


Measured memory_bytes: 1024
n, W = map(int,input().split())
dp = [[float('inf') for i in range(10**5+1)] for j in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0
ans = 0
for i in range(1, n+1):
    w, v = map(int,input().split())
    for j in range(1, 10**5+1):
        if v>j:
            dp[i][j] = dp[i-1][j]
            continue
        dp[i][j] = min(dp[i-1][j], w+dp[i-1][j-v])
        if dp[i][j] <= W:
            ans = max(ans, j)
print(ans)

Measured memory_bytes: 269148
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<cstring>
#include<cctype>
#include<complex>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<functional>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<bitset>
using namespace std;
const int dx[] = {1,0,-1,0};
const int dy[] = {0,1,0,-1};
#define INF 1e+8
#define EPS 1e-10
#define PB push_back
#define fi first
#define se second
#define ll long long 
#define reps(i,j,k) for(int i = (j); i < (k); i++)
#define rep(i,j) reps(i,0,j)
typedef pair<int,int> Pii;
typedef vector<int> vi;
bool PRIME[1000001];
void Prime(){ 
    PRIME[0]=PRIME[1]=true; 
    for(int i=2;i*i <= 1000000 ;i++){ 
        if(PRIME[i]==false){ 
            for(int j=i*i ; j<=1000000 ; j+=i){ 
                PRIME[j] = true; 
            } 
        } 
    } 
    return; 
}
int main(){
	Prime();
    int n,x;
    while(scanf("%d%d",&n,&x),n){
        int goods[32]={0};
		int dp[1000001]={0};
		int ans = -1;
        rep(i,n){
            scanf("%d",&goods[i]);
        }
		rep(i,n){
			reps(j,goods[i],x+1){
				if(dp[j] < dp[j-goods[i]]+goods[i]){
					dp[j] = dp[j-goods[i]]+goods[i];
					if(!PRIME[dp[j]])ans = max(ans,dp[j]);
				}
			}
		}
		ans == -1 ? puts("NA") : printf("%d\n",ans);
	}
    return 0;
}

Measured memory_bytes: 6088
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] s = new int[n];
        int[] h = new int[n];
        for (int i = 0; i < n; i++) h[i] = sc.nextInt();

        int cnt = 0;
        boolean flag = false;

        while (true) {
            flag = false;
            for (int i = 0; i < n; i++) {
                if (s[i] != h[i]) {
                    s[i] += 1;
                    flag = true;
                } else if (s[i] == h[i] && flag) {
                    cnt += 1;
                    flag = false;

                }
            }
            if (flag) cnt += 1;
            if (Arrays.equals(s, h)) break;
        }
        System.out.println(cnt);
    }
}


Measured memory_bytes: 23252
x, y = map(int, input().split())

result = 0

if x == 1:
    result += 300000
elif x == 2:
    result += 200000
elif x == 3:
    result += 100000
if y == 1:
    result += 300000
elif y == 2:
    result += 200000
elif y == 3:
    result += 100000
if x == 1 and y == 1:
    result += 400000
print(result)

Measured memory_bytes: 3064
'use strict'

class PriorityQueue {
  constructor () {
    this.heap = []
  }
  push (n) {
    let i = this.heap.length++, j
    while (i) {
      j = i - 1 >> 1
      if (this.heap[j] <= n) break
      this.heap[i] = this.heap[j]
      i = j
    }
    this.heap[i] = n
  }
  pop () {
    const dest = this.top()
    const last = this.heap.pop()
    const k = this.size() >> 1
    let i = 0, j
    while (i < k) {
      j = (i << 1) + 1
      if (this.heap[j+1] < this.heap[j]) ++j
      if (last <= this.heap[j]) break
      this.heap[i] = this.heap[j]
      i = j
    }
    if (this.size()) this.heap[i] = last
    return dest
  }
  size () {return this.heap.length}
  top () {return this.heap[0]}
}

function main(inp) {
  inp = inp.trim().split('\n')
  const NM = inp.shift().split(' ').map(n => Number(n))
  inp = inp.map(r => r.split(' ').map(n => Number(n)))
  inp.push([1e9,0])
  inp.sort((a,b)=>a[0]-b[0])

  let ans = 0
  let j = 0
  let pq = new PriorityQueue()
  for (let i = 1; i <= NM[1]; i++) {
    while (inp[j][0] <= i) {
      pq.push(-inp[j][1])
      j++
    }
    if (pq.size()) ans -= pq.pop()
  }
  console.log(ans)
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));


Measured memory_bytes: 53212
import java.util.*;
public class Main{
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    String s[] = new String[n];
    for(int i=0 ; i<n ; i++){
      s[i] = sc.next();
    }
    int countAC = 0;
    int countWA = 0;
    int countTLE = 0;
    int countRE = 0;

    for(int i=0 ; i<n ; i++){
      if(s[i].equals("AC")){
        countAC++;
      }else if(s[i].equals("WA")){
        countWA++;
      }else if(s[i].equals("TLE")){
        countTLE++;
      }else{
        countRE++;
      }
    }
    System.out.println("AC x " + countAC);
    System.out.println("WA x " + countWA);
    System.out.println("TLE x " + countTLE);
    System.out.println("RE x " + countRE);
  }
}


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

#define N 100005
#define endl '\n'
typedef long long ll;

int n, ev[N][4];
int dp[N][5];

int f(int i, int last){
  if(i==n+1) return 0;
  if(dp[i][last]!=-1) return dp[i][last];
  
  int maxi=0;
  for(int j=1; j<=3; j++){
    if(j==last) continue;
    maxi=max(maxi, ev[i][j]+f(i+1, j));
  }
  return dp[i][last]=maxi;
}

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

  cin >> n;
  for(int i=1; i<=n; i++){
    cin >> ev[i][1] >> ev[i][2] >> ev[i][3];
    dp[i][1]=dp[i][2]=dp[i][3]=-1;
  }
  dp[1][0]=-1;

  cout << f(1, 0) << endl;
}

Measured memory_bytes: 11648