akhauriyash/Code-Regression huggingface dataset:
(function () {
  var input = '';

  function main () {
    var inputLen,
        i,
        n,
        z;
    
    for (i = 0, inputLen = input.length - 1; i < inputLen; i += 1) {
      n = parseInt(input[i], 10);
      if (n === 0) {
        break;
      } else {
        z = zero(n);
        console.log(z);
      }
    }
  }

  function zero (f) {
    var j,
        zeroCnt = 0;

    for (j = f; j / 5 !== 0; j /= 5) {
      zeroCnt += Math.floor(j / 5);
    }

    return zeroCnt;
  }
  
  process.stdin.resume();
  process.stdin.setEncoding('utf8');
  process.stdin.on('data', function (chunk) {
    input += chunk;
  });

  process.stdin.on('end', function () {
    input = input.split('\n');
    main();
  });
}());

Measured memory_bytes: 9496
#include <cstdio>
#include <iostream>
using namespace std;
inline int read() {
	int w = 1,res = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9') {
		if(ch == '-') w = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
	return w * res;
}
long long dp[50][150000], ans = 1, mod = 1e9 + 7;
int main() {
	int n = read(), x = read(), y = read(), z = read();
	int st = (1 << (x + y + z - 1)) | (1 << (y + z - 1)) | (1 << (z - 1));
	int sum = (1 << (x + y + z)) - 1;
	dp[0][0] = 1;
	for(int i = 1; i <= n; i ++) {
		ans *= 10;
		ans %= mod;
		for(int j = 0; j <= sum; j ++) {
			if(dp[i - 1][j] == 0) continue;
			for(int k = 1; k <= 10; k ++) {
				int a = (j << k) | (1 << k - 1);
				a &= sum;
				if((a & st) != st)
					dp[i][a] = (dp[i][a] + dp[i - 1][j]) % mod;
			}
		}
	}
	for(int j = 0; j <= sum; j ++)
		ans = (ans - dp[n][j] + mod) % mod;
	cout << ans;
	return 0;
}

Measured memory_bytes: 40940
#include <bits/stdc++.h>
#define int LL
using namespace std;
typedef long long LL;
const int MAX_N=200005;
struct edge
{
	int u,v,cost;
	edge(){}
	edge(int _u,int _v,int _cost)
	{
		u=_u;
		v=_v;
		cost=_cost;
	}
	bool operator < (const edge &A) const 
	{
		return cost<A.cost;
	} 
};
const LL INF=0x3f3f3f3f3f3f3f3f;
LL A[MAX_N];
LL ans,n,D;
int fa[MAX_N];
LL Ai_Di[MAX_N],Aj_Dj[MAX_N];
vector <edge> g;
void init()
{
	for(int i=0;i<n;i++)fa[i]=i;
}
int find(int x)
{
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
void unite(int u,int v)
{
	fa[find(u)]=find(v);
}
bool same(int u,int v)
{
	return find(u)==find(v);
}
void solve(int l,int r)
{
	if(l==r)return;
	int mid=(l+r)/2;
	int pl=-1;
	LL vl=INF;
	for(int i=l;i<=mid;i++)
	{
		if(Ai_Di[i]<vl)
		{
			vl=Ai_Di[i];
			pl=i;
		}
	}
	int pr=-1;
	LL vr=INF;
	for(int i=mid+1;i<=r;i++)
	{
		if(Aj_Dj[i]<vr)
		{
			vr=Aj_Dj[i];
			pr=i;
		}
	}
	for(int i=l;i<=mid;i++)
	{
		g.push_back(edge(i,pr,vr+Ai_Di[i]));
	}
	for(int i=mid+1;i<=r;i++)
	{
		g.push_back(edge(i,pl,vl+Aj_Dj[i]));
	}
	solve(l,mid);
	solve(mid+1,r);
}
signed main()
{
	cin>>n>>D;
	init();
	for(int i=0;i<n;i++)cin>>A[i];
	for(int i=0;i<n;i++)Ai_Di[i]=A[i]-D*i;
	for(int i=0;i<n;i++)Aj_Dj[i]=A[i]+D*i;
	solve(0,n-1);
	sort(g.begin(),g.end());
	for(int i=0;i<g.size();i++)
	{
		int u=g[i].u;
		int v=g[i].v;
		int cost=g[i].cost;
		if(!same(u,v))
		{
			unite(u,v);
			ans+=cost;
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 106848
def parse(s):
    first_val = None
    verticals, horizontals = list(), list()
    seq = 0
    is_horizontal = True
    is_first = True
    for c in s:
        if c == 'T':
            if is_first:
                first_val = seq
                is_first = False
            elif is_horizontal:
                horizontals.append(seq)
            else:
                verticals.append(seq)
            is_horizontal = not is_horizontal
            seq = 0
        else:
            seq += 1
    if seq > 0:
        if is_first:
            first_val = seq
        elif is_horizontal:
            horizontals.append(seq)
        else:
            verticals.append(seq)
    return first_val, verticals, horizontals


def check(vals, target):
    val_set = {0}
    for v in vals:
        tmp_set = set()
        for sv in val_set:
            tmp_set.add(sv + v)
            tmp_set.add(sv - v)
        val_set = tmp_set
    return target in val_set


def main():
    S = input()
    X, Y = list(map(int, input().split(' ')))
    fv, vs, hs = parse(S)
    if check(hs, X - fv) and check(vs, Y):
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()


Measured memory_bytes: 3596
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);
		
		int x = stdIn.nextInt();
		
		if(x==7 || x == 5  || x ==3) {
			System.out.println("YES");
		}else {
			System.out.println("NO");
		}
		
		
		
	}

}


Measured memory_bytes: 23764
import bisect
import numpy as npy
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
n0,np,nn = 0,0,0
for i in a:
  if i>0:  np += 1
  elif i == 0:  n0 += 1
  else:  nn += 1
kp = (np**2-np+nn**2-nn)//2
k0 = n0*(n-n0)+(n0**2-n0)//2
kn = nn*np
if kn < k <= kn+k0:
  print(0)
  exit()
nls = []
pls = []
for i in range(n):
  if a[i] < 0:
    nls.append(a[i])
  elif a[i] > 0:
    pls.append(a[i])
ln = len(nls)
lp = len(pls)
nls = npy.array(nls,dtype=npy.int64)
pls = npy.array(pls,dtype=npy.int64)
if k <= kn:
  l = a[0]*a[-1]-1
  r = 0
  while l+1 < r:
    m = (l+r)//2
    mls = m//nls
    tmp = npy.searchsorted(pls,mls,side="right").sum()
    if tmp > kn-k:
      l = m
    else:
      r = m
  print(l)
else:
  nls = -nls
  nls = nls[::-1]
  k -= kn+k0
  l = 0
  r = max(a[0]**2,a[-1]**2)+1
  while l+1 < r:
    m = (l+r)//2
    tmp  = npy.searchsorted(nls,m//nls,side="right").sum()
    tmp += npy.searchsorted(pls,m//pls,side="right").sum()
    tmp -= npy.searchsorted(nls**2,m,side="left")
    tmp -= npy.searchsorted(pls**2,m,side="left")
    if tmp >= 2*k:
      r = m
    else:
      l = m
  print(r)

Measured memory_bytes: 32316
#include <stdio.h>
#include <string.h>
 
int n, q;
int l, r;
int sum[100005];
char str[100005];
 
int main()
{
	int len;
 
	scanf("%d %d", &n, &q);
	scanf("%s", str);
 
	len = strlen(str);
	for (int i = 1; i < len; i++) {
		if (str[i - 1] == 'A' && str[i] == 'C') {
			sum[i] = sum[i - 1] + 1;
		} else {
			sum[i] = sum[i - 1];
		}
	}
 
 
	for (int i = 0; i < q; i++) {
		scanf("%d %d", &l, &r);
		l--;
	    r--;
 
		printf("%d\n", sum[r] - sum[l]);
	}
 
	return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define irep(i, n) for (int i = n; i >= 0; i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1 << 30;
int a[100002]; 
int main() {
	int n;
	cin >> n;
	rep(i, n) {
		int x; cin >> x;
		if (x == 0) {
			a[0]++; a[1]++;
		} else {
			a[x-1]++; a[x]++; a[x+1]++;
		}
	}
	int ma = -1;
	rep(i, 100002) {
		ma = max(ma, a[i]);
	}
	cout << ma << endl;
	return 0;
}

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

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int N;
	int i;
	int a[1000], b[1000], c[1000];
	int hozon[1000] = {0};
	
	scanf("%d", &N);
	
	for (i = 0; i < N; i++){
		scanf("%d %d %d", &a[i], &b[i], &c[i]);
	}
	
	for (i = 0; i < N; i++){
		if (a[i] * a[i] == b[i] * b[i] + c[i] * c[i]){
			hozon[i] = 1;
		}
		else if (b[i] * b[i] == a[i] * a[i] + c[i] * c[i]){
			hozon[i] = 1;
		}
		else if (c[i] * c[i] == b[i] * b[i] + a[i] * a[i]){
			hozon[i] = 1;
		}
	}
	
	for (i = 0; i < N; i++){
		if (hozon[i] == 1){
			printf("YES\n");
		}
		else {
			printf("NO\n");
		}
	}
	
	return (0);
}

Measured memory_bytes: 596
/// kAAzuki Hoshino
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
typedef long long ll;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
//#define inf 1000000000
#define mod 1000000007
#define dmp(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl
#define fs first
#define sc second
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define mt make_tuple
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
    return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
    o<<"{";
    for(const T& v:vc) o<<v<<",";
    o<<"}";
    return o;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

 
string s;
int ans = 0, cnt = 0;

signed main(){
IOS;
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
	
	cin >> s;
	int n = s.size();
	int cur = 1;
	vi v;
	for(int i=1;i<n;i++){
		if(s[i]==s[i-1]){
			cur++;
		}
		else {
			v.pb(cur);
			cur = 1;
		}
	}        
  v.pb(cur);
  int idx = 0;
  vi res;
  if(s[0]=='>'){
  	ans += ((v[0]*(v[0]+1))/2);
  	idx++;
  	int k = v.size();
  	for(int i=1;i<k;i++)res.pb(v[i]);
  }
	else res = v;
  int k = res.size();
  if(k%2){
  	int x = res.back();
  	res.pop_back();
  	ans+= (x*(x+1))/2;
  	k--;
  }
  //cout << ans << endl;
  //cout << res << endl;
  for(int i=0;i<res.size();i+=2){
  	int mx = max( res[i], res[i+1] );
  	int mn = min( res[i], res[i+1] );
  	ans+= (mx*(mx+1))/2;
  	mn--;
  	ans+= (mn*(mn+1))/2;
  }
  cout << ans << endl;

return 0;
}
///....


Measured memory_bytes: 5780
import java.util.Scanner;

public class Main {

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

	Scanner sc = new Scanner(System.in);

	boolean[] table ;
	{
		table = new boolean[100101];
		for(int i = 0; i * i <= 100100; i++){
			table[i*i] = true;
		}
	}
	
	void run() {
		int a = sc.nextInt();
		int b = sc.nextInt();
		
		
		System.out.println(table[Integer.valueOf(String.valueOf(a)+String.valueOf(b))]?"Yes":"No");
		

	}
}


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

int main()
{
 int x, y, z ;
 cin>>x>>y>>z;
 if(x==y){
    cout<<z;
 }
 if(x==z){
    cout<<y;
 }
 if(y==z){
    cout<<x;
 }
    return 0;
}


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

bool find_sub(string s, string t)
{
	int n = s.size(), m = t.size();
	
	for (int i = 0; i < n - m; ++i)
		if (s.substr(i, m) == t)
			return true;
	
	return false;
}

int main()
{
	string s, t;
	cin >> s >> t;
	cout << (find_sub(s + s, t) ? "Yes" : "No");
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define rep(i,n) for(ll i=0; i<(n); ++i)
#define ALL(x) x.begin(),x.end()
typedef long long int ll;

int main(){
    int n; cin >> n;
    vector<ll> a(n); rep(i,n) cin >> a[i];
    sort(ALL(a));
    reverse(ALL(a));
    
    ll ans = 0;
    for(int i=1;i<n;i++){
        ans += a[i/2];
    }
    cout << ans <<endl;
    return 0;
}

Measured memory_bytes: 4848
from math import log,ceil
def solve():
    N,K = map(int, input().split())
    # if N == 1 and K != 1:
    #     print("0")
    #     exit()
        
    # elif N == 1 and K ==  1:
    #     print("1")
    #     exit(0)

    
    ans = 0
    for x in range(1, N+1): # xは初期値
        kaisuu = ceil( log( K / x, 2))
        # tmp = pow(0.5, kaisuu)
        tmp = 1/N
        for i in range(kaisuu):
            tmp *= 0.5
        ans += tmp 
    # ans /= N
    print(ans)
        

    
if __name__ == "__main__":
    solve()


Measured memory_bytes: 2940
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <random>
#include <iomanip>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<pair<ll,ll> > vpll;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
typedef map<int,int> mii;
typedef set<int> si;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define arep(i,v) for(auto i : v)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define STLL(s) strtoll(s.c_str(), NULL, 10)
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int
// #define endl '\n';
#define fi first
#define se second
#define NONVOID [[nodiscard]]
constexpr int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
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;}
template <class T> inline void dump(T &v){irep(i, v){cout<<*i<<((i==--v.end())?'\n':' ');}}
inline string getline(){string s; getline(cin,s); return s;}
inline void yn(const bool b){b?fin("yes"):fin("no");}
inline void Yn(const bool b){b?fin("Yes"):fin("No");}
inline void YN(const bool b){b?fin("YES"):fin("NO");}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX;
constexpr ll LLINF = 1LL<<60;
constexpr ll MOD = 1000000007;
constexpr double EPS = 1e-9;



int main() {

    int h,w;
    cin>>h>>w;
    vvi dp(h,vi(w,0));
    vvi v(h,vi(w));
    rep(i,h)rep(j,w)cin>>v[i][j];
    rep(i,h)rep(j,w)dp[i][j]=1-v[i][j];
    int ans=0;
    for(int i=1;i<h;i++){
        for(int j=1;j<w;j++){
            if(v[i][j])continue;
            dp[i][j]=min({dp[i-1][j-1],dp[i-1][j],dp[i][j-1]})+1;
            // chmax(ans,dp[i][j]);
        }
    }

    rep(i,h)rep(j,w)chmax(ans,dp[i][j]);
    // rep(i,h)dump(dp[i]);
    fin(ans*ans);
}


Measured memory_bytes: 18128
#define P(x) cout << #x" = " << x << endl
#define PP(x, y) cout << "("#x", "#y") = (" << x << ", " << y << ")" << endl
#define PPP(x, y, z) cout << "("#x", "#y", "#z") = (" << x << ", " << y << ", " << z << ")" << endl

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;
int n;
int a[100000];
int b[100000];
int c[100000];
int main(){
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> c[i];
    }
    sort(a, a + n);
    sort(b, b + n);
    sort(c, c + n);
    ll ans =0;
    for (int i = 0; i < n; ++i) {
        int mid = b[i];
        // P(mid);
        ans += (ll)distance(a, lower_bound(a, a + n, mid)) *
        (ll)distance(upper_bound(c, c + n, mid), c + n);
    }
    cout << ans << endl;
}

Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, n) for(int i=0; i<int(n); i++)
#define RNG(i, f, t) for(int i=int(f); i<=int(t); ++i)
#define REV(i, f, t) for(int i=int(f); i>=int(t); --i)
#define ALL(v) (v).begin(), (v).end()
bool RELAXED = false;
template<int,typename T> struct MINMAX{ T val; MINMAX(T val) : val(val) {} };
template<typename T> MINMAX<1,T> MAX(T val) { return MINMAX<1,T>(val); };
template<typename T> MINMAX<2,T> MIN(T val) { return MINMAX<2,T>(val); };
template<typename T, typename U> inline T& operator|=(T &lhs, MINMAX<1,U> rhs) { return lhs = (rhs.val > lhs ? (RELAXED=true,rhs.val) : (RELAXED=false,lhs)); }
template<typename T, typename U> inline T& operator|=(T &lhs, MINMAX<2,U> rhs) { return lhs = (rhs.val < lhs ? (RELAXED=true,rhs.val) : (RELAXED=false,lhs)); }
template<typename T> inline vector<T> readVector(int n) { vector<T> vec(n); FOR(i,n) cin>>vec[i]; return vec; }
template<typename T> void EXIT(T answer) { cout<<answer<<endl; exit(0); }
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef signed long long int ll;

const int MAXN=305;
double dp[MAXN][MAXN][MAXN];

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

    int n; cin>>n;
    vi pile = readVector<int>(n);

    int A = count(pile.begin(), pile.end(), 1);
    int B = count(pile.begin(), pile.end(), 2);
    int C = count(pile.begin(), pile.end(), 3);

    FOR(c,n+1)
    FOR(b,n+1)
    FOR(a, n+1)
    {
        int empty = n-a-b-c;
        double ezeroes = 1/(1-1.*empty/n) - 1;
        if(a>0)
            dp[a][b][c] += 1.*a/(a+b+c) * (1+ezeroes + dp[a-1][b][c]);
        if(b>0)
            dp[a][b][c] += 1.*b/(a+b+c) * (1+ezeroes + dp[a+1][b-1][c]);
        if(c>0)
            dp[a][b][c] += 1.*c/(a+b+c) * (1+ezeroes + dp[a][b+1][c-1]);
    }

    cout<<setprecision(12)<<dp[A][B][C]<<endl;
    return 0;
}



Measured memory_bytes: 219392
#include<cstdio>
using namespace std;
int a[200010],b[200010];
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}
	int start = n / 2;
	int start1 = n / 2-1;
	int ch = 0;
	if (n % 2)
		ch = 1;
	b[start] = a[0];
	start++;
	for (int i = 1; i < n; i++) {
		if (ch % 2==0)
		{
			b[start1] = a[i];
			if(start)
				start1--;
		}
		else {
			b[start] = a[i];
			start++;
		}
		ch++;
	}
	for (int i = 0; i < n; i++)
		printf("%d ", b[i]);
}

Measured memory_bytes: 3712
def dfs(res, chk):
    if len(res) == n:
        global idx
        global pi
        global qi
        idx += 1
        pb = all(res[i]+1 == p for i, p in enumerate(P))
        qb = all(res[i]+1 == q for i, q in enumerate(Q))
        if pb:
            pi = idx
        if qb:
            qi = idx
        return
    
    for i in range(n):
        if chk & (1 << i):
            continue
        else:
            dfs(res + [i], chk^(1 << i))

n = int(input())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
idx = 0
pi = qi = 0
perm = []
dfs([], 0)
print(abs(pi-qi))

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    int n;
    int a,b;
    int dif;
  
    cin >> n >> a >> b;

    dif = b - a - 1;
  
    if (dif % 2 == 1) { 
       cout << "Alice" << endl;
    }
    else { 
       cout << "Borys" << endl;
    }

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
//#include "boost/multiprecision/cpp_int.hpp"
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2

ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
typedef pair<dd,dd> d_d;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fi first
#define se second
#define endl "\n"
#define SORT(v) sort(v.begin(),v.end())
#define ERASE(v) v.erase(unique(v.begin(),v.end()),v.end())
#define POSL(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define POSU(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
//template<class T>void max(T a,T b){if(a<b)return b;else return a;}
//template<class T>void min(T a,T b){if(a>b)return b;else return a;}
//template<class T>bool Max(T&a, T b){if(a < b){a = b;return 1;}return 0;}
//template<class T>bool Min(T&a, T b){if(a > b){a = b;return 1;}return 0;}

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



int main(){fastio
    ll n,k;cin>>n>>k;
    ll ans=k;
    rep(i,1,n-1)ans=ans*(k-1);
    cout<<ans<<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);
        int n = sc.nextInt();
        int num = n;
        int s = 0;
        while(num != 0){
            s += num % 10;
            num /= 10;
        }
        System.out.println(n % s == 0? "Yes":"No");
    }
}


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

int main() {
  int N;
  cin >> N;
  
  vector<int> vec(N);
  vector<int> point(N);
  vector<int> bonus(N);
  
   for (int i = 0; i < N; i++) {
  cin >> vec.at(i);
}
   for (int i = 0; i < N; i++) {
  cin >> point.at(i);
}
   for (int i = 0; i < N; i++) {
  cin >> bonus.at(i);
}
  
  long long int cou =0;
  
   for (int i = 0; i < N-1; i++) {
  cou += point.at(i);
     if(vec.at(i) +1==vec.at(i+1)){
              cou += bonus.at(vec.at(i)-1);
   }
   }
  
cout << cou+point.at(N-1) << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <queue>
using namespace std;
int w, h, n;
char map[1024][1024];
// 各点到当前工厂的距离
int d[1024][1024];
const int direction[4][2] = {
	{ -1, 0 },
	{ 1, 0 },
	{ 0, -1 },
	{ 0, 1 },
};
 
int factory[16][2];
typedef pair<int, int> P;
 
 
 
//************************************
// Method:    bfs
// FullName:  bfs
// Access:    public 
// Returns:   int
// Qualifier:
// Parameter: const int & sx 起点x
// Parameter: const int & sy 起点y
// Parameter: const int & gx 终点x
// Parameter: const int & gy 终点y
//************************************
int bfs(const int& sx, const int& sy, const int& gx, const int& gy)
{
	//memset(d, -1, sizeof(d));
	for (int i = 0; i < h; ++i)
	{
		for (int j = 0; j < w; ++j)
		{
			d[j][i] = -1;
		}
	}
	queue<P> que;
	que.push(P(sx, sy));
	d[sx][sy] = 0;
	while (que.size())
	{
		const P p = que.front(); que.pop();
		// 如果是终点就结束
		if (p.first == gx && p.second == gy)
		{
			break;
		}
 
		// 四方向漫游
		for (int i = 0; i < 4; ++i)
		{
			int nx = p.first + direction[i][0];
			int ny = p.second + direction[i][1];
			// 是否可以移动，并且该点没有访问过
			if (0 <= nx && nx < w && 0 <= ny && ny < h && map[nx][ny] != 'X' && d[nx][ny] == -1)
			{
				que.push(P(nx, ny));
				d[nx][ny] = d[p.first][p.second] + 1;
			}
		}
	}
 
	return d[gx][gy];
}
 
///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
 
	cin >> h >> w >> n;
	for (int i = 0; i < h; ++i)
	{
		for (int j = 0; j < w; ++j)
		{
			cin >> map[j][i];
		}
	}
 
	for (int i = 0; i < h; ++i)
	{
		for (int j = 0; j < w; ++j)
		{
			if (map[j][i] == 'S')
			{
				factory[0][0] = j;
				factory[0][1] = i;
				map[j][i] = '.';
			}
			else if (isdigit(map[j][i]))
			{
				int index = map[j][i] - '0';
				factory[index][0] = j;
				factory[index][1] = i;
			}
		}
	}
 
	int step = 0;
	for (int i = 0; i < n; ++i)
	{
		// 按顺序吃遍中华
		step += bfs(factory[i][0], factory[i][1], factory[i + 1][0], factory[i + 1][1]);
	}
	
	cout << step << endl;
 
	return 0;
}
///////////////////////////End Sub//////////////////////////////////


Measured memory_bytes: 8124
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

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

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

// Self settings
// clang-format off
#define MAX_N 1000000
#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
#define SLN(i,N) (i == N-1 ? "\n" : " ")
// clang-format on

char S[MAX_N + 1];
int ans[MAX_N];

void solve()
{
  int n = strlen(S);

  int even = 0, odd = 0;
  int t = 0;
  while (t < n) {
    int cnt = 0;
    // Find R near by L
    while (S[t] == 'R' && t < n) {
      t++, cnt++;
    }
    cnt++;
    int r = t - 1, l = t;
    int d = (cnt + 1) / 2;
    ans[l] += d;
    ans[r] += cnt - d;

    cnt = 0;
    // L の間すすめる
    while (S[t] == 'L' && t < n) t++, cnt++;
    t--, cnt--;
    d = (cnt + 1) / 2;
    ans[r] += d;
    ans[l] += cnt - d;
    t++;
  }
  REP(i, n) cout << ans[i] << SLN(i, n);
}

int main(void)
{
  cin >> S;
  solve();
  return 0;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
typedef long long LL;
#define SORT(c) sort((c).begin(),(c).end())

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

using namespace std;
int main(void)
{
  for(;;){
    int n;
    cin >> n;
    if(!n) return 0;
    vector<pair<int,int> >guy(n,make_pair(0,0));
    REP(i,n){
      int m;
      cin >> m >> guy[i].first;
      REP(j,m){
	int s,e;
	cin >> s >> e;
	FOR(k,s,e) guy[i].second=guy[i].second|(1<<k-6);
      }
    }
    vector<int> score(65536,0);
    REP(i,n){
      REP(j,1<<16){
	if(j&guy[i].second) continue;
	score[j|guy[i].second]=max(score[j|guy[i].second],score[j]+guy[i].first);
      }
    }
    int answer=0;
    REP(j,1<<16) answer=max(answer,score[j]);
    cout << answer << endl;
  }
}

Measured memory_bytes: 3272
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const int INF = pow(10, 7);
int main(){
  int n;cin>>n;
  vector<double> v(n);
  for(int i=0;i<n;i++){
    cin>>v[i];
  }
  while((int)v.size()>1){
    sort(v.begin(), v.end());
  	v.push_back((v[0]+v[1])*0.5);
    v.erase(v.begin());
    v.erase(v.begin());
  }
  cout<<fixed<<setprecision(7)<<v[0]<<endl;
}

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

int main() {
  int x;
  cin >> x;
  cout << ((x >= 30)? "Yes":"No") << endl;
  return 0;
}

Measured memory_bytes: 3588
#include "bits/stdc++.h"

using namespace std;

#define print(s) cout << (s) << endl;
#define sp(x) cout<<setprecision(x);
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n) 
#define all(a) (a).begin(), (a).end()
#define inf 10000000
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a, b, c;cin>>a>>b>>c;
    if(c>=a&&c<=b){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
return 0;
}

Measured memory_bytes: 256
#!usr/bin/env python3
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect

def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def LS(): return [list(x) for x in sys.stdin.readline().split()]


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


def LIR(n):
    return [LI() for i in range(n)]


def SR(n):
    return [S() for i in range(n)]


def LSR(n):
    return [LS() for i in range(n)]


sys.setrecursionlimit(1000000)
mod = 1000000007


def solve():
    n, k = LI()
    flag_list = [False] * n
    for _ in range(k):
        d = I()
        a = LI()
        for i in range(d):
            flag_list[a[i]-1] = True
    print(flag_list.count(False))
    
    return


if __name__ == "__main__":
    solve()


Measured memory_bytes: 68088
def main():
    h, n = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(n)]

    large_num = 10**9
    dp = [large_num] * (h + 10**4 + 1)
    dp[0] = 0
    for abe in ab:
        a = abe[0]
        b = abe[1]
        for i1 in range(h + 1):
            if dp[i1 + a] > dp[i1] + b:
                dp[i1 + a] = dp[i1] + b
    r = min(dp[h:])

    print(r)

if __name__ == '__main__':
    main()


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

int main() {
  long long a, b, c;
  std::cin >> a >> b >> c;

  long long d = c - a - b;

  if (d >= 0 && 4* a * b < d * d) {

    std::cout << "Yes" << std::endl;
  } else {
    std::cout << "No" << std::endl;
  }

  return 0;
}


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

class Solve
{
    static void Main(string[] args) {
        var S = Console.ReadLine();
        var set = new HashSet<char>();
        var answer = string.Empty;
        foreach (var let in S) {
            if (set.Contains(let)) {
                answer = "no";
                break;
            }
            set.Add(let);
        }
        if (set.Count == S.Length) answer = "yes";
        var writer = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false};
        Console.SetOut(writer);
        Console.WriteLine(answer);
        Console.Out.Flush();
    }
}

Measured memory_bytes: 26164
use std::io;

fn main() {
    let _n = read::<i32>();
    let mut a = read_vec::<i32>();

    let count = selection_sort(&mut a);
    print_vec(a.to_vec());
    println!("{}", count);
}

/// 選択ソート
/// 左から順に最小の値を検索しては入れていく
/// https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/2/ALDS1_2_B
pub fn selection_sort<T: Ord + Copy + std::fmt::Display>(x: &mut [T]) -> usize{
    let mut count = 0;
    for i in 0..x.len() {
        let mut minj = i;
        for j in i+1..x.len() {
            if x[j] < x[minj] {
                minj = j;
            }
        }
        x.swap(i, minj);
        if i != minj { count += 1; }
    }
    count
}

fn print_vec<T: std::fmt::Display>(v: Vec<T>) {
    for a in &v[0..v.len() - 1] {
        print!("{} ", a);
    }
    println!("{}", v[v.len() - 1]);
}

/// 標準入力から一行を読み取り、指定の型に変換する関数
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

/// 標準入力から一行を読み取り、空白文字で分割し、各要素を指定の型に変換する関数
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut line = String::new();
    io::stdin().read_line(&mut line)
        .ok()
        .expect("Faild to read Vec");
    line.trim().split_whitespace()
        .map(|i| i.parse().ok().unwrap()).collect()
}


Measured memory_bytes: 5036
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#define ll long long
#define inf 1<<30
#define il inline 
#define in1(a) read(a)
#define in2(a,b) in1(a),in1(b)
#define in3(a,b,c) in2(a,b),in1(c)
#define in4(a,b,c,d) in2(a,b),in2(c,d)
il void readl(ll &x){
    x=0;ll f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
il void read(int &x){
    x=0;int f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
using namespace std;
/*===================Header Template=====================*/
int n;
string s,last;
map <string,int> mp;
int main(){
	int i;
	read(n);
	cin>>s;
	mp[s]=1;
	last=s;
	for(i=2;i<=n;i++){
		cin>>s;
		if(mp[s]||last[last.length()-1]!=s[0]){
			printf("No");
			return 0;
		}
		mp[s]=1;
		last=s;
	}
	printf("Yes");
	return 0;
}

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

int main()
{
    long long width, height, x, y;
    cin >> width >> height >> x >> y;
    double sqr = (double)(width) * height/2;
    cout <<fixed<<setprecision(10)<< sqr << " ";
    
   
    if(x*2 == width && y * 2 == height){
      cout << 1 << endl;
    }else {
          cout << 0 << endl;
    } 
}



Measured memory_bytes: 256
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, k = LI()
sqt = int(n ** 0.5)
dp_mul_num = [1] * sqt + [n // i - n // (i + 1) for i in range(1, n // sqt)][::-1]
group_num = len(dp_mul_num)
dp = [[0] * group_num for _ in range(k)]
dp[0] = dp_mul_num





for i in range(k - 1):
    ret = 0
    for j in range(group_num):
        ret = (ret + dp[i][j]) % mod
        dp[i + 1][group_num - j - 1] = ret * dp_mul_num[group_num - j - 1] % mod











print(sum(dp[-1]) % mod)

Measured memory_bytes: 92796
#include <iostream>
#define M 100

using namespace std;

int main()
{
	int m, n, i, j,sum;
	int A[M][M];
	int B[M];

	cin >> m >> n;
	for (i = 0; i < m; i++)
	{
		for (j=0;j<n;j++)
		{
			cin >> A[i][j];
		}
	}
	for (i = 0; i < n; i++)
	{
		cin >> B[i];
	}

	for (i=0;i<m;i++)
	{
		sum=0;
		for (j=0;j<n;j++)
		{
			sum += A[i][j] * B[j];
		}
		cout << sum << endl;
	}
	return 0;
}



Measured memory_bytes: 3140
/*
#include<cstdio>
const int N = 1e5;
int n, a, b, c;
int vis[N];
int main() {
	return 0;
}
*/
#include<cstdio>
#include<cmath>
const int N = 120;
int x, a[1000];
int main() {
	scanf("%d", &x);
	for (int i = -120; i <= 120; i++) a[i + N] = i * i * i * i * i;
	for (int i = -120; i <= 120; i++)
		for (int j = -120; j <= 120; j++)
			if (a[i + N] - a[j + N] == x) return printf("%d %d", i, j), 0;
	return 0;
}

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

template <typename InputIterator>
typename InputIterator::value_type
summation(InputIterator first, InputIterator last) {
  using T = typename InputIterator::value_type;
  T *p = new T();
  const auto sum = std::accumulate(first, last, *p);
  delete p;
  return sum;
}
template <typename T>
std::istream& operator>> (std::istream &stream, std::vector<T> &v);
template <typename T1, typename T2>
std::istream& operator>> (std::istream &stream, std::pair<T1, T2> &p);
template <typename T>
std::istream& operator>> (std::istream &stream, std::vector<T> &v) {
  for (auto &i : v) {
    stream >> i;
  }
  return stream;
}
template <typename T1, typename T2>
std::istream& operator>> (std::istream &stream, std::pair<T1, T2> &p) {
  stream >> p.first >> p.second;
  return stream;
}

int main() {
  int64_t x;
  std::cin >> x;
  int64_t i = x / 11;
  x %= 11;

  if (x == 0) {
    std::cout << 2 * i << std::endl;
  } else if (x <= 6) {
    std::cout << 2 * i + 1 << std::endl;
  } else {
    std::cout << 2 * i + 2 << std::endl;
  }
  return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
                try {
			int num = Integer.parseInt(new String(in.readLine()));
			System.out.println(num * num * num);
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
}



Measured memory_bytes: 24296
#include<stdio.h>
int main(void)
{
	char s[3];

	for (int i = 0; i < 3; i++) {
		scanf("%c", &s[i]);
	}
	int count = 0;
	for (int i = 0; i < 3; i++) {
		//printf("%c", s[i]);
		if (s[i] == 'o') {
			count++;
		}
	}
	int sum;

	sum = 700 + count * 100;

	printf("%d", sum);

	return 0;
}

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

using namespace std;

#define M 1046527

class Hash{
    vector<string> h;

    int getChar(char ch){
        if ( ch == 'A') return 1;
        else if ( ch == 'C') return 2;
        else if ( ch == 'G') return 3;
        else if ( ch == 'T') return 4;
    }

/* convert a string into an integer value */
    long long getKey(string str){
        long long sum = 0, p = 1, i;
        for ( i = 0; i < str.size(); i++ ){
            sum += p*(getChar(str[i]));
            p *= 5;
        }
        return sum;
    }

    int h1(int key){ return key % M; }
    int h2(int key){ return 1 + (key % (M - 1)); }


public:
    Hash() : h(M) {}

    void insert(string str){
        long long i,key;
        i = getKey(str);
        for (int j = 0;; j++) {
            key = (h1(i) + j * h2(i)) % M;
            if (h[key] == str) {
                return;
            } else if (h[key].empty()){
                h[key] = str;
                return;
            }
        }
    }
    bool find(string str){
        long long i,key;
        i = getKey(str);
        for (int j = 0;; j++) {
            key = (h1(i) + j * h2(i)) % M;
            if (h[key] == str) {
                return true;
            } else if (h[key].empty()){
                return false;
            }
        }
    }
};

int main(){
    //freopen("in", "r", stdin);

    Hash h;

    vector<int> data(19);

    int n;
    cin >> n;
    for (int j = 0; j < n; ++j) {
        string s;
        string k;
        cin >> s >> k;
        if (s == "insert"){
            h.insert(k);
        } else {
            string result = h.find(k) ? "yes" : "no";
            cout << result << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 27172
#include "bits/stdc++.h"
using namespace std;

// GNU C Compiler
//template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }


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

	type

--------------------------------------------
*/
using LL = long long;
using ULL = unsigned long long;
//using pair<T1, T2> = p12;

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

	container

--------------------------------------------
*/
#define PB emplace_back
#define MP make_pair 
#define SZ(a) int((a).size())

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

	repetition

--------------------------------------------
*/
#define REP(n) for(int i=0; i<n; i++)
#define REPj(n) for(int j=0; j<n; j++)
#define REPinit(a,n) for(int i=a; i<n; i++)
#define REPinitj(a,n) for(int j=a; j<n; j++)

//algorithm
//#define SORT(c) sort((c).begin(),(c).end())

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

	constant

--------------------------------------------
*/
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

/*

	Optimizer

*/
//#pragma GCC optimize("Ofast")

int main(int argc, char const *argv[])
{
    
  ULL a,b,x;
  cin >> a >> b >> x;

  ULL bx = b/x+1;
  ULL ax;
  if(a == 0LL) {
    ax = 0;
  }
  else {
    ax = (a-1)/x+1;
  }
  
  cout << (bx - ax) << endl;

  return 0;
}


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




	int main()
	{
	   
	   


	    ios_base::sync_with_stdio(false);
	    cin.tie(NULL);
	    
	    ll k;
	    cin>>k;
	    ll count = 0;
	    for(ll i=1;i<=k;i++)
	    {
	    	for(ll j=1;j<=k;j++)
	    	{
	    		for(ll j1=1;j1<=k;j1++)
	    		{
	    			count = count + __gcd(i,__gcd(j,j1));
	    		}
	    	}
	    }
	    cout<<count<<endl;
	 
	    return 0;
	}

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

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

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

int GCD(int a, int b){
    if(b == 0) return a; 
    if(a < b) return GCD(b, a);
    else return GCD(b, a%b);
}

struct Edge{
    int to;
    long cost;
    Edge(int t, long c){
        to = t;
        cost = c;
    }
};
typedef pair<long, int> P;//距離、点

struct Dijkstra{
    int V;
    vector<vector<Edge>> G;
    vector<long> d;
    long inf = 1000000000000000000; // 10^18

    Dijkstra(int vv){
        V = vv;
        G.resize(V);
        d.resize(V);
    }

    void add_data(int a, int b, long c){
        Edge e1(b, c);
        G[a].push_back(e1);
    }

    void calc_dis(int s){
        priority_queue<P, vector<P>, greater<P>> que; //Pのfirstが小さい奴から取り出せる
        REP(i, V) d[i] = inf;
        d[s] = 0l;
        que.push(P(0, s));

        while(!que.empty()){
            P p = que.top(); que.pop();
            int v = p.second;
            if(d[v] < p.first) continue;
            for(int i=0;i<G[v].size();i++){
                Edge e = G[v][i];
                if(d[e.to] > d[v] + e.cost){
                    d[e.to] = d[v] + e.cost;
                    que.push(P(d[e.to], e.to));
                }
            }
        }
    }


};

int main()
{   
    int n, m, s, t; cin >> n >> m >> s >> t;
    s--, t--;
    Dijkstra d1(n), d2(n);
    REP(i, m){
        int u, v; cin >> u >> v;
        long a, b; cin >> a >> b;
        d1.add_data(u-1, v-1, a);
        d1.add_data(v-1, u-1, a);
        d2.add_data(u-1, v-1, b);
        d2.add_data(v-1, u-1, b);
    }
    d1.calc_dis(s);
    d2.calc_dis(t);
    long money[100005];
    money[n-1] = d1.d[n-1] + d2.d[n-1];
    for(int i=n-2; i>=0; i--){
        money[i] = min(money[i+1], d1.d[i] + d2.d[i]);
    }
    REP(i, n) cout << 1000000000000000l - money[i] << endl;

    return 0;
}



Measured memory_bytes: 19068
while True:
    try:
        N=int(input())
        if N==0:break
        ans=[]
        dic={}
        for i in range(N):
            e,p,q=map(int,input().split())
            if e in dic:dic[e] +=p*q
            else:dic[e]=p*q
        for v,m in dic.items():
            if m>=1000000:ans.append(v)
        if len(ans)==0:ans.append("NA")
        for k in ans:
            print(k)
    except:break


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

int main() {
  int N,M;
  cin >> N >> M;
  if (N>=M) {
      cout << 0 << endl;
  }  
  else {
      vector<int> vec(M);
      for (int i = 0; i < M ;i++) {
          cin >> vec.at(i);
      }

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

      vector<int> dist(M-1);
      for (int i = 0; i < M -1; i++) {
          dist.at(i) = vec.at(i+1) - vec.at(i);
      }

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

      int ans = 0;
      for (int i = 0; i < M-1-(N-1);i++){
          ans += dist.at(i);
      } 
      cout << ans << endl;
  }
} 

Measured memory_bytes: 1024
import math


def solve(n):
    if n == 2:
        return 1
    res = 0

    # divisor of n - 1
    m = int(math.sqrt(n - 1))
    for i in range(2, m + 1):
        if (n - 1) % i == 0:
            res += 2
    if m * m == n - 1:
        res -= 1
    res += 1

    # divisor of n
    # n itself
    res += 1
    divisors = []
    m = int(math.sqrt(n))
    for i in range(2, m):
        if n % i == 0:
            divisors.append(i)
            divisors.append(n // i)
    if n % m == 0 and m * m == n:
        divisors.append(m)
    elif n % m == 0:
        divisors.append(m)
        divisors.append(n // m)
    # print(divisors)
    for p in divisors:
        q = n // p
        while q % p == 0:
            q = q // p
        if q % p == 1:
            res += 1
    # print(res)
    return res


def solve_greed(n):
    for p in range(2, n + 1):
        m = n
        while m % p == 0:
            m = m // p
        if m % p == 1:
            print(p)


def main():
    n = int(input())
    res = solve(n)
    print(res)


def test():
    assert solve(6) == 3
    assert solve(3141) == 13
    assert solve(314159265358) == 9


if __name__ == "__main__":
    test()
    main()


Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> using vt = vector<T>;
template<class T> using vvt = vector<vt<T>>;
template<class T> using ttt = tuple<T,T>;
using tii = tuple<int,int>;
using tiii = tuple<int,int,int>;
using vi = vector<int>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define mt make_tuple
#define ALL(a) (a).begin(),(a).end()
#define FST first
#define SEC second
#define DEB cerr<<"!"<<endl
#define SHOW(a,b) cerr<<(a)<<" "<<(b)<<endl
const int INF = (INT_MAX/2);
const ll LLINF = (LLONG_MAX/2);
const double eps = 1e-8;
const ll DIV =1e9+7;
//const double PI = M_PI;
inline ll pow(ll x,ll n,ll m){ll r=1;while(n>0){if((n&1)==1)r=r*x%m;x=x*x%m;n>>=1;}return r%m;}
inline ll lcm(ll d1, ll d2){return d1 / __gcd(d1, d2) * d2;}
#define chmax(a,b) a=max(a,b)

/*Coding Space*/
map<ll,ll> t;
int main(){
  int n,m; cin >> n >> m;
  t[0] = 0;
  rep(i,m){
    ll a,b; cin >> a >> b;
    int s = 0;
    rep(i,b){int c; cin >> c; s |= (1<<(c-1));}
    map<ll, ll> tt;
    tt = t;
    for(auto l : t){
      auto ind = l.FST; auto cost = l.SEC;
      if(tt.count(s|ind))tt[s|ind] = min(tt[s|ind], cost + a);
      if(tt[s|ind] == 0)  tt[s|ind] = cost + a;
    }
    t = tt;
  }
  ll s = (1 << n) - 1;
  if(t[s] == 0) cout << -1 << endl;
  else cout << t[s] << endl;
}


Measured memory_bytes: 768
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<bitset>
#include<math.h>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int N=200000+100;
const db pi=acos(-1.0);
#define lowbit(x) ((x)&(-x))
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define go(u,i) for (register int i=head[u],v=sq[i].to;i;i=sq[i].nxt,v=sq[i].to)
#define fir first
#define sec second
#define mkp make_pair
#define pb push_back
#define maxd 998244353
#define eps 1e-8
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 readll()
{
    ll x=0;int 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;
}

struct hnode{int id,c0,c1;};
bool operator <(hnode p,hnode q) {return 1ll*p.c0*q.c1<1ll*q.c0*p.c1;}
priority_queue<hnode> q;
int n,val[N],p[N],fa[N],c0[N],c1[N],siz[N];

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

int main()
{
    n=read();
    rep(i,2,n) p[i]=read();
    rep(i,1,n) val[i]=read();
    rep(i,1,n) {fa[i]=i;siz[i]=1;}
    rep(i,2,n)
    {
        if (!val[i]) {fa[i]=find(p[i]);siz[fa[i]]++;}
    }
    ll ans=0;
    rep(i,1,n)
    {
        if (!val[i]) continue;
        c1[i]=1;c0[i]=siz[i]-1;ans+=(siz[i]-1);
        if (i!=1) q.push((hnode){i,siz[i]-1,1});
    }
    //cout << ans << endl;
    //rep(i,1,n) cout << find(i) << " ";cout << endl;
    while (!q.empty())
    {
        hnode u=q.top();q.pop();
        int id=u.id,nxtfa=find(p[id]);
        //cout << "merge " << id << " " << nxtfa << endl;
        if ((nxtfa==0) || (c1[id]!=u.c1)) continue;
        ans+=1ll*c1[nxtfa]*u.c0;
        fa[id]=nxtfa;c0[nxtfa]+=u.c0;c1[nxtfa]+=u.c1;
        q.push((hnode){nxtfa,c0[nxtfa],c1[nxtfa]});
    }
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 8944
#include<bits/stdc++.h>
#define ll long long
#define N 100010
#define pb push_back
using namespace std;
struct Info{int x,y;}a[N];
int b[N],n,ans;
map<int,int> s;
bool c1(const Info &a,const Info &b){return a.y<b.y;}
bool c2(const int &a,const int &b){return a<b;}
int main(){
	cin>>n;
	for (int i=1;i<=n;i++)cin>>a[i].x;
	for (int i=1;i<=n;i++)cin>>a[i].y;
	sort(a+1,a+n+1,c1);
	for (int i=1;i<=n;i++)b[i]=a[i].x;
	sort(b+1,b+n+1,c2);
	for (int i=1;i<=n;i++){
		if (b[i]>a[i].y){puts("No");return 0;}
		if (i<n&&b[i+1]<=a[i].y)ans=1;
	}
	if (ans)puts("Yes");
	else{
		for (int i=1;i<=n;i++)s[a[i].x]=i;
		int no=1,nu=0;
		while (no!=1||nu==0){
			nu++;
			no=s[b[no]];
		}
		if (nu==n) puts("No");else puts("Yes");
	}
	return 0;
}

Measured memory_bytes: 6144
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,c,r=0;
  cin>>n;
  map<int,int> m;
  for(int i=0;i<n;++i){cin>>c;m[c]++;}
  for(auto&& p:m)r+=p.second-p.first*(p.second>=p.first);
  cout<<r;
  return 0;
}

Measured memory_bytes: 4736