akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<long long, long long> P;
struct edge{long long to,cost;};
const int inf = 1 << 27;
const long long INF = 1LL << 60;
const int COMBMAX = 1001001;
const long long MOD = 1000000007;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define eachdo(v, e) for(const auto& e : (v))
#define all(v) (v).begin(), (v).end()
#define lower_index(v, e) (long long)distance((v).begin(), lower_bound((v).begin(), (v).end(), e))
#define upper_index(v, e) (long long)distance((v).begin(), upper_bound((v).begin(), (v).end(), e))
long long mpow(long long a, long long n, long long mod = MOD){long long res = 1; while(n > 0){if(n & 1)res = res * a % mod; a = a * a % mod; n >>= 1;} return res;}
void yn(bool j){cout << (j ? "Yes" : "No") << endl; return;}
template<class Head> void pt(Head&& head){cout << head << endl; return;}
template<class Head, class... Tail> void pt(Head&& head, Tail&&... tail){cout << head << " "; pt(forward<Tail>(tail)...);}
template<class T> void debug(T v){rep(i, v.size()) cout << v[i] << " " ; cout << endl;}
template<class T> void debug2(T v){rep(i, v.size()){rep(j, v[i].size()) cout << v[i][j] << " " ; cout << endl;}}
template<class T1, class T2> long long bcount(T1 v, T2 a){return upper_index(v, a) - lower_index(v, a);} 
template<class T1, class T2> inline bool chmin(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}
template<class T1, class T2> inline bool chmax(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

int main(){
    ll D, G; cin >> D >> G;
    vector<ll> p(D), c(D);
    rep(i, D) cin >> p[i] >> c[i];
    ll ans = INF;
    rep(i, 1 << D){
        ll cnt = 0;
        ll score = 0;
        rep(j, D){
            if (i >> j & 1){
                score += (j + 1) * 100 * p[j];
                score += c[j];
                cnt += p[j];
            }
        }

        for(ll j = D - 1; 0 <= j; --j){
            if (((i >> j) ^ 1) & 1){
                rep(k, p[j] - 1){
                    if (G <= score){
                        chmin(ans, cnt);
                    }
                    score += (j + 1) * 100;
                    cnt++;
                }
            }
        }
        if(G <= score) chmin(ans, cnt);
    }
    pt(ans);
}

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


int main()
{

  ios::sync_with_stdio(0);
  cin.tie(0);
  int h,w,m,x,y;
  cin>>h>>w>>m;
  map<int,int> r,c;
  map<pair<int,int>,int> grid;
  pair<int,int> p;
  while(m--){
    cin>>x>>y;
    r[x]++;
    c[y]++;
    p.first=x;
    p.second=y;
    grid[p]=1;
  }
  vector<int> dx,dy;
  map<int,int>::iterator it;
  ll mr=0,mc=0;
  for(it=r.begin();it!=r.end(); it++){
    mr=max(mr,(ll)it->second);
  }
  for(it=c.begin();it!=c.end(); it++){
    mc=max(mc,(ll)it->second);
  }
  for(it=r.begin();it!=r.end(); it++){
      if(it->second==mr){dx.push_back(it->first);}
  }
  for(it=c.begin();it!=c.end(); it++){
    if(it->second==mc){dy.push_back(it->first);}
  }
  ll ans=mr+mc-1;
  for(int i=0; i<dx.size(); i++){
     for(int j=0; j<dy.size(); j++){
         p.first=dx[i];
         p.second=dy[j];
         if(grid[p]==0){cout<<ans+1; return 0;}
     }
  }
  cout<<ans;

  return 0;
}

Measured memory_bytes: 54280
n, k = map(int, input().split())
a = list(map(int, input().split()))

dct = {}
for i in range(n):
    if a[i] in dct:
        dct[a[i]] += 1
    else:
        dct[a[i]] = 1
select_num = len(dct) - k
if select_num <= 0:
    print(0)
    exit()
sorted_dct = sorted(dct.items(), key=lambda x:x[1])
ans = 0
for i in range(select_num):
    ans += sorted_dct[i][1]
print(ans)

Measured memory_bytes: 42740
#include<bits/stdc++.h>
using namespace std; 
typedef long long ll;
#define pb push_back
#define fi first
#define se second 


typedef long double ld ;
struct pt {
	ld x,y; 
	pt operator+(pt p) {return {x+p.x, y+p.y};}
	pt operator-(pt p) {return {x-p.x, y-p.y};}
	pt operator*(ld d) {return {x*d, y*d};}
	pt operator/(ld d) {return {x/d, y/d};}
};
ostream& operator<<(ostream& os, pt p) {
	return os << "("<< p.x << "," << p.y << ")";
}
vector<pt>intrsct;
pt perp(pt p) {return {-p.y, p.x};}
ld sq(pt p){return p.x*p.x + p.y*p.y;}
bool prnt;
ld ds(pt p){
	return hypot(p.x,p.y);
}
void circleCircle(pt o1, ld r1, pt o2, ld r2) {
	pt d=o2-o1;
	double d2=sq(d);
	if (d2 == 0) {return ;} // concentric circles	
	double pd = (d2 + r1*r1 - r2*r2)/2; // = |O_1P| * d
	double h2 = r1*r1 - pd*pd/d2; // = hˆ2
	if (h2 >= 0) {
		pt p = o1 + d*pd/d2, h = perp(d)*sqrt(h2/d2);
		if(prnt){
			cout<<o1<<" "<<o2<<endl;
			cout<<r1<<" "<<r2<<endl;
			cout<<p<<" "<<h<<endl;
			cout<<p-h<<" "<<p+h<<endl;
			cout<<ds(p+h-o1)<<" "<<ds(p+h-o2)<<endl;
			cout<<ds(p-h-o1)<<" "<<ds(p-h-o2)<<endl;
			cout<<"-------------------------"<<endl;
			
		}
		intrsct.pb(p+h);
		intrsct.pb(p-h);
	}
}
pt c[66];
ld r[66];
ld rr[66];
int n,k;
bool ch(ld x){
	prnt = false;
	for(int i=0;i<n;i++){
		rr[i] = x/r[i];
	}
	intrsct.clear();
	for(int i=0;i<n;i++){
		intrsct.pb(c[i]);
		for(int j=0;j<n;j++){
			circleCircle(c[i],rr[i],c[j],rr[j]);
		}
	}
	for(pt p:intrsct){
		int cnt = 0;
		for(int i=0;i<n;i++){
			if(ds(p-c[i])<=rr[i]+1e-9)cnt++;
		}
		if(cnt>=k)return true;
	}
	return false;
}
void chh(ld x){
	prnt = true;
	cout<<"CHK "<<x<<endl;
	for(int i=0;i<n;i++){
		rr[i] = x/r[i];
		cout<<rr[i]<<" ";
	}
	cout<<endl;
	intrsct.clear();
	for(int i=0;i<n;i++){
		intrsct.pb(c[i]);
		for(int j=0;j<n;j++){
			circleCircle(c[i],rr[i],c[j],rr[j]);
//			pt p1 = intrsct.back();
		}
	}
	for(pt p:intrsct){
		cout<<p<<" : "<<endl;;
		int cnt = 0;
		for(int i=0;i<n;i++){
			cout<<i<<" ";
			cout<<ds(p-c[i])<<" "<<rr[i]<<endl;
			if(ds(p-c[i])<=rr[i]+1e-9)cnt++;
		}
		cout<<endl;
	}
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cout<<fixed<<setprecision(14);
	cin>>n>>k;
	for(int i=0;i<n;i++){
		ld x,y; 
		cin>>x>>y;
		c[i] = {x,y};
		cin>>r[i];
	}
	ld ans = 0;
	if(k==1){
		cout<<ans<<endl;
		return 0;
	}
	ld st = 0;
	ld en = 1e12;
	for(int i=0;i<200;i++){
		ld mid = (st+en)/2;
		if(ch(mid)){
			en = mid;
		}else{
			st = mid;
		}
		
	}
	cout<<st<<endl;
	return 0;
}


Measured memory_bytes: 640
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]

# n = int(input())
# a, b
# s = input()


N, K = map(int, input().split())
ans = 0
cnt = 0

i = N
while i > 0:
    if i >= K:
        ans += pow(0.5, cnt) / N
        i -= 1
    else:
        K = (K + 1) // 2
        cnt += 1
    
print(ans)



Measured memory_bytes: 39664
#include<stdio.h>
#include<string.h>
char h[12][50010];
int a,b,d[50010],m[50010];
int Y[]={1,2,-1};
int O[]={0,1,-1};
int f(int s,int t){//printf("%d %d %d %d\n",s,t,d[s],m[t]);
  int n,i;
  if(t==b+1&&s==a)return 1;
  if(t>b||s>=a)return 0;
  if((b+1-t)*2<a-s)return 0;
  for(i=0;i<3;i++){
    n=s+Y[i];
    if(n<0||n>a)continue;
    if((d[n]+O[i]+12)%12-m[t]&&n<a)continue;
    //if(h[t][n])continue;
    //h[t][n]=1;
    if(f(n,t+1))return 1;
    //h[m[t]][t+1]=0;
  }
  return 0;
}
int main(){
  int n,i,j;
  char s[3],o[][3]={"C","C#","D","D#","E","F","F#","G","G#","A","A#","B"};
  scanf("%d",&n);
  while(n--){
    scanf("%d %d",&a,&b);
    for(i=0;i<12;i++){
      for(j=0;j<50010;j++)h[i][j]=0;
    }
    for(i=0;i<a;i++){
      scanf("%s",s);
      for(j=0;strcmp(s,o[j]);j++);
      d[i]=j;
    }
    for(i=0;i<b;i++){
      scanf("%s",s);
      for(j=0;strcmp(s,o[j]);j++);
      m[i]=j;
    }
    d[a]=m[b]=-1;
    printf("%s\n",f(-1,0)?"Yes":"No");
  }
  return 0;
}

Measured memory_bytes: 4696
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<ll, int> P;
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 main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	map<char, int> mp;
	string s;
	cin >> s;
	rep(i,s.size()){
		++mp[s[i]];
	}
	rep(i,n-1){
		map<char, int> mp2;
		cin >> s;
		rep(i,s.size()){
			++mp2[s[i]];
		}
		for(auto p : mp){
			chmin(mp[p.first], mp2[p.first]);
		}
	}
	string ans = "";
	for(auto p : mp){
		rep(i,p.second) ans += p.first;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3636
ma = lambda :map(int,input().split())
ni = lambda:int(input())
import collections
import math
import fractions
gcd = fractions.gcd
n,m = ma()
s = input()
t = input()
l = m*n //gcd(m,n)
ln = []
for i in range(n):
    ln.append((l//n*i+1,s[i]))

for i in range(m):
    ln.append((l//m*i+1,t[i]))
ln.sort()
prev=-1
wp = ""
for num,w in ln:
    if num==prev:
        if w ==wp:
            pass
        else:
            print(-1)
            exit()
    prev=num
    wp = w
print(l)


Measured memory_bytes: 24416
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void) {
    int h, m, s, S;
    scanf("%d", &S);
    h = S / 3600;
    m = (S % 3600) / 60;
    s = S % 60;
    printf("%d:%d:%d\n",h,m, s);
    return 0;
}


Measured memory_bytes: 2060
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <string>
#include <map>
#include <list>
using namespace std;

int main() {
  long long N,A,B;
  cin >> N >> A >> B;

  long long sum=0,res=0;

  for(int i = 1; i <= N; ++i){
    int ii=i;
    while(ii != 0){
      sum += ii%10;
      ii /= 10;
    }
    if(sum >= A && sum <= B){
      res += i;
    }
    sum=0;
  }
  cout << res << endl;
}



Measured memory_bytes: 3572
#C_Walking Takahashi 
X,K,D = map(int,input().split())
X = abs(X)
step = min(K,int(X/D))
K -= step
X -= step * D
if (K % 2 == 0):
    out = X
else:
    out = D - X
   
# 出力
print(out)

Measured memory_bytes: 9164
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    var ans = n
    for (six in 0..n) {
        var count = 0
        var six = six
        var nine = n - six
        while (six > 0) {
            count += six % 6
            six /= 6
        }
        while (nine > 0) {
            count += nine % 9
            nine /= 9
        }
        ans = Math.min(ans, count)
    }
    println(ans)
}

Measured memory_bytes: 31828
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i];if(i<len-1) s<<" ";
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i]<<endl;
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){
	s<<"{ ";
	for(auto itr=v.begin();itr!=v.end();++itr) {
		if (itr!=v.begin()) {s<< ", ";}
		s<<(*itr);
	}
	s<<" }";
	return s;
}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){
	s<<"{"<<endl;
	for(auto itr=m.begin();itr!=m.end();++itr){
		s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;
	}
	s<<"}"<<endl;
	return s;
}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double PI=acos(-1);
const double EPS=1e-10;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	vector<int> p(n);
	int ans=0,mi=INF;
	rep(i,n){
		cin>>p[i];
		chmin(mi,p[i]);
		if(mi==p[i]) ans++;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <stdlib.h>

int compare_int(const void *a,const void *b){
  if(*(long long*)a > *(long long*)b) return 1;
  return -1;
}

int main(void){
  long long N, C, K;
  scanf("%lld%lld%lld", &N, &C, &K);

  long long T[N];
  for (int i = 0; i < N; i++) {
    scanf("%lld", &T[i]);
  }

  qsort(T, N, sizeof(long long), compare_int);

  int ans = 0, cnt = 0, time = T[0];
  for (int i = 0; i < N; i++) {
    cnt++;
    if(time+K < T[i]){
      ans++;
      cnt = 1;
      time = T[i];
    }else if(cnt == C){
      ans++;
      cnt = 0;
      time = T[i+1];
    }
  }
  if(cnt != 0) ans++;

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

  return 0;
}

Measured memory_bytes: 1788
# -*- coding:utf-8 -*-
HW = list(map(int, input().split()))
c = [input() for i in range (HW[0])]
ans = []
for i in range( HW[0] ):
    ans.append(c[i])
    ans.append(c[i])
for i in range ( 2*HW[0] ):
    print(ans[i])


Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
#define ll long long
using namespace std;
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
const int N = 2100,mod = 1e9 + 7;
int n,m,tot,X;
ll ans,res;
int QAQ[N],fa[N];
struct node{int fr,to,val;} a[N << 1];
int cmp(node a,node b){return a.val < b.val;}
int find(int x){return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);}
ll getans(int now)
{
	ll rt = 0;
	for(int i = 1;i <= m;i ++)
	{
		if(find(a[i].fr) == find(a[i].to)) continue;
		rt += a[i].val; now ++;
		fa[find(a[i].fr)] = find(a[i].to);
		if(now == n - 1) return rt;
	}
	return rt;
}
ll ksm(ll x,int y){ll re = 1; for(;y;y >>= 1,x = x * x % mod) if(y & 1) re = re * x % mod; return re;}
signed main()
{
	n = read(); m = read(); X = read();
	for(int i = 1;i <= m;i ++){a[i].fr = read(); a[i].to = read(); a[i].val = read();}
	for(int i = 1;i <= n;i ++) fa[i] = i;
	sort(a + 1,a + 1 + m,cmp); ans = getans(0);
	if(ans > X) {puts("0"); return 0;}
	if(ans == X) res = (res + 1ll * (ksm(2ll,n - 1) - 2ll) * ksm(2ll,m - n + 1) % mod) % mod;
	for(int i = 1;i <= m;i ++)
	{
		for(int j = 1;j <= n;j ++) fa[j] = j;
		fa[find(a[i].fr)] = find(a[i].to);
		QAQ[i] = getans(1) + a[i].val;
	}
	sort(QAQ + 1,QAQ + 1 + m);
	for(int i = n;i <= m;i ++) if(QAQ[i] == X) res = (res + ksm(2ll,m - i + 1)) % mod;
	cout << res << "\n";
}

Measured memory_bytes: 384
#include <string>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
 
int main(){
    int k,n;
    cin >> n >> k;
    int a[n];
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    int b=n-1;
    int c=k-1;
    cout << (b+c-1)/c  << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <iostream>
#include<math.h>
using namespace std;
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; }
int main()
{
    int A, B, C;
    cin >> A >> B >> C;
    vector<bool>amari(B, false);
    bool is_can = false;
    int count = 2;
    int moto_A = A;
    while (true) {
        if (A % B == C) {
            is_can = true;
            break;
        } else if (amari[A%B]) {
            break;
        }

        amari[A%B] = true;
        A = moto_A * count;
        count++;
    }

    if (is_can) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}

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

int main(){
    long long n;
    cin >> n;

    int a, b;
    int ans = 9999999;
    int size = sqrt(n)*1000;
    for(int i=1; i < size; i++){
        int digit_a = 0;
        int digit_b = 0;
        if(n % i == 0){
            a = n / i;
            b = i;
            while(a != 0){
                digit_a += 1;
                a /= 10;
            }
            while(b != 0){
                digit_b += 1;
                b /= 10;
            }
            ans = min(ans, max(digit_a, digit_b));
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import fractions

n, m = map(int, input().split())
a = list(map(int, input().split()))
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

def lcm(x, y):
	return (x * y) // gcd(x, y)

now = a[0]
for i in range(1, n):
	now = lcm(now, a[i])
	if now > 2 * m:
		print(0)
		exit(0)

for i in range(n):
	if (now//a[i])%2 == 0:
		print(0)
		exit(0)

print(((m//(now//2))+1)//2)


Measured memory_bytes: 89580
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>

#define pb push_back
#define mp make_pair

using namespace std;

template<typename T>inline void upmin(T &x,T y) { y<x?x=y:0; }
template<typename T>inline void upmax(T &x,T y) { x<y?x=y:0; }

typedef unsigned int u32;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double lod;
typedef pair<int,int> PR;
typedef vector<int> VI;

const lod pi=acos(-1);
const int oo=1<<30;
const LL OO=1e18;

int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}

int main()
{
	LL k,d;cin>>k;d=k/50;k%=50;
	puts("50");
	for (int i=0;i<k;i++)
		cout<<50-i+d<<" ";
	for (int i=k+1;i<=50;i++)
		cout<<50-i+d<<" ";
	return 0;
}


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

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

#define ll      long long
#define Fi      first
#define Se      second
#define Pb      push_back
#define vi      vector<int>
#define vs      vector<string>
#define vp      vector<pair<int,int>>
#define vvi     vector<vector<int>>
#define vvp     vector<vector<pair<int,int>>>
using Graph  =  vector<vector<int>>; //Caution!! Segmentation Fault!! Don't forget to add +1!

#define sz(x) (int)x.size()
#define all(v) v.begin(),v.end()
#define output_s(s) printf("%s\n",(s).c_str())

#define rep(i,n)        for(int i=0;i<(int)(n);i++)
#define Rep(i,n,m)      for(int i=(int)(n);i<(int)(m);i++)
#define RepS(i,n,m)     for(int i=(int)(n);i<=(int)(m);i++)
#define RRepS(i,n,m)    for(int i=(int)(n);i>=(int)(m);i--)
#define SRepS(i,n,m)    for(int i=(int)(n);i*i<=(int)(m);i++)
#define RepA(x)         for(auto &item:(x))

void CINT(){} //@shibh308's template
template<class Head,class... Tail> void CINT(Head&& head,Tail&&... tail){cin>>head; CINT(move(tail)...);}    
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)
#define VCIN(x) for(auto &item:x) cin>>item

void OUT(){}
template<class Head,class...Tail> void OUT(Head&& head,Tail&&...tail){cout<<head<<(sizeof...(tail)?" ":"\n"); OUT(move(tail)...);}
#define COUT(...) OUT(__VA_ARGS__)

template<typename TypeInt>TypeInt GCD(TypeInt a,TypeInt b){return a%b==0?b:GCD(b,a%b);} //最大公約数
template<typename TypeInt>TypeInt LCM(TypeInt a,TypeInt b){return a*b/GCD(a,b);} //最小公倍数
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}
template<class T>bool comp(T a,T b){return abs(a)<abs(b);} //比較関数

void YES(bool f){printf(f?"YES\n":"NO\n");}
void Yes(bool f){printf(f?"Yes\n":"No\n");}
void Possible(bool f){printf(f?"Possible\n":"Impossible\n");}
void POSSIBLE(bool f){printf(f?"POSSIBLE\n":"IMPOSSIBLE\n");}

//----------------------library------------------------//

//const int dx[4]={1,0,-1,0};
//const int dy[4]={0,1,0,-1};
const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};
const int NMAX = 200;
const int INF = 1e9;
const int MOD = 1e9+7;
bool flag;

//----------------------Global-------------------------//

signed main(){
    LCIN(A,B,C,D);
    A--;
    ll cur=GCD(C,D);
    ll a=A-(A/C+A/D-A/(C*D/cur));
    ll b=B-(B/C+B/D-B/(C*D/cur));
    printf("%lld\n",b-a);

    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#include<stack>
using namespace std;

int main(){
	long long x,a,b;
	cin >> x >> a >> b;
	long long m = b - a;
	if(m <= 0) cout << "delicious";
	else if(m < x + 1) cout << "safe";
	else if(m >= x + 1) cout << "dangerous";
}

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

int main() {
  int n, q;
  cin >> n >> q;

  queue<psi> process;
  rep(i, n) {
    string p;
    int t;
    cin >> p >> t;
    psi pt = make_pair(p, t);
    process.push(pt);
  }

  int total_time = 0;
  while (!process.empty()) {
    psi p = process.front();
    process.pop();
    if (p.second <= q) {
      total_time += p.second;
      cout << p.first << " " << total_time << endl;
    } else {
      total_time += q;
      p.second -= q;
      process.push(p);
    }
  }

  return 0;
}


Measured memory_bytes: 6384
#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, k;
  cin >> n >> k;
  map<int,int> num;
  rep(i,n) {
    int A;
    cin >> A;
    num[A]++;
  }
  vector<int> a;
  for(auto p: num) {
    a.push_back(p.second);
  }
  sort(a.begin(),a.end());
  int i=0, cnt=0;
  k = num.size()-k;
  while(i<k) {
    cnt += a.at(i);
    i++;
  }
  cout << cnt << endl;
}


Measured memory_bytes: 10748
#include <iostream>
#include <algorithm>
#include <array>
int main(int argc,char **argv){
  std::array<int,3> a;
  for(int i=0;i<3;i++){
    std::cin>>a[i];
  }
  std::sort(a.begin(),a.end(),std::greater<int>());
  printf("%d\n",a[2]+a[1]);
  return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Threading;

using Pair = System.Collections.Generic.KeyValuePair<int, int>;

class Program
{
	public Program() { }

	static void Main(string[] args)
	{
		new Program().prog();
	}

	Scanner cin;

	const int MOD = 1000000007;
	const int INF = int.MaxValue - 10;
	const long INFL = long.MaxValue - 10;
	const double EPS = 1e-8;
	const double PI = 3.1415926536;
	int[,] dir8;
	int[,] dir4;

	int N;
	int[] A, B;

	void prog()
	{
		cin = new Scanner();
		dir8 = new int[8, 2] { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, -1 }, { 0, 1 }, { 1, -1 }, { 1, 0 }, { 1, 1 } };
		dir4 = new int[4, 2] { { -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 } };

		N = cin.nextInt();
		A = new int[N];
		B = new int[N+1];

		for (int i = 0; i < N; i++)
		{
			A[i] = cin.nextInt();
			B[A[i]] = i;
		}
		UnionFind uf = new UnionFind(N + 1);
		long ans = 0;
		for (int i = N; i > 0; i--)
		{
			int idx = B[i];
			ans += A[idx];
			if (idx - 1 >= 0 && A[idx - 1] > A[idx])
			{
				ans += uf.unite(idx, idx - 1) * A[idx];
			}
			if (idx + 1 < N && A[idx + 1] > A[idx])
			{
				ans += uf.unite(idx, idx + 1) * A[idx];
			}
		}
		Console.WriteLine(ans);
	}

	class UnionFind
	{
		int N;
		int[] parent;
		int[] rank;
		int[] size;

		public UnionFind(int N)
		{
			this.N = N;
			parent = new int[N];
			rank = new int[N];
			size = new int[N];
			for (int i = 0; i < N; i++)
			{
				parent[i] = i;
				size[i] = 1;
			}
		}

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

		public long unite(int x, int y)
		{
			x = find(x);
			y = find(y);
			long s = (long)size[x] * size[y];
			if (rank[x] < rank[y])
			{
				parent[x] = y;
				size[y] += size[x];
			}
			else
			{
				parent[y] = x;
				size[x] += size[y];
				if (rank[x] == rank[y]) rank[x]++;
			}
			return s;
		}

		public bool same(int x, int y)
		{
			return find(x) == find(y);
		}
	}
}

class Scanner
{
	string[] s;
	int i;

	char[] cs = new char[] { ' ' };

	public Scanner()
	{
		s = new string[0];
		i = 0;
	}

	public string next()
	{
		if (i < s.Length) return s[i++];
		string st = Console.ReadLine();
		while (st == "") st = Console.ReadLine();
		s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
		i = 0;
		return next();
	}

	public int nextInt()
	{
		return int.Parse(next());
	}

	public long nextLong()
	{
		return long.Parse(next());
	}

	public double nextDouble()
	{
		return double.Parse(next());
	}
}

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

#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define mod 1000000007
#define inf 1000000000000000001
#define all(c) c.begin(),c.end()
#define mp(x,y) make_pair(x,y)
#define mem(a,val) memset(a,val,sizeof(a))
#define eb emplace_back
#define f first
#define s second

using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

/*****************************************************START******************************************************************/



int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
	 //cin >> T;
	// cin.ignore(); must be there when using getline(cin, s)
	while (T--)
	{
		int ans = -1;
		for(int i=0; i<5; i++){
			int a;  cin >> a; 
			if(a == 0){
				ans = i+1;
			}
		}
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h> 
using namespace std;
const int mxn = 1e7 , N = 5e5 + 5 , mod = 1e9 + 7;
long long dp[10005][105][2];
bool vis[10005][105][2];
string s;
int siz , n;
long long sol(int idx,int d,int state){
	if(idx==siz){
		if(d==0)
			return 1;
		return 0;
	}
	
	if(vis[idx][d][state]){
		return dp[idx][d][state];
	}
	vis[idx][d][state] = true;
	long long ret = 0;
	if(state){
		for(int i = 0;i<=s[idx]-'0';i++){
			if(i==s[idx]-'0'){
				ret = (ret + sol(idx+1,(d-(i%n)+n)%n,1))%mod;
				continue;
			}
			ret = (ret + sol(idx+1,(d-(i%n)+n)%n,0))%mod;
		}
	}else{
		for(int i = 0;i<=9;i++){
			ret = (ret + sol(idx+1,(d-(i%n)+n)%n,0))%mod;
		}
	}
	
	return dp[idx][d][state] = ret;
}  
int main(){
	cin>>s>>n;
	siz = s.size();
	cout<<(((sol(0 , 0 , 1) - 1) %mod)+ mod) %mod;
	return 0;
}


Measured memory_bytes: 22860
listInput = list(map(int,input().split()))
count5=0
count7=0
for i in listInput:
    if i==5:
        count5+=1
    if i==7:
        count7+=1
    else:
        continue

if count5==2 and count7==1:
    print("YES")
else:
    print("NO")






Measured memory_bytes: 2940
#include <iostream>
#include <vector>
#include <stack>
#include <string>
#include <map>
#include <ctime>
#include <list>
#include <bitset>
#include <algorithm>

#define ll long long
#define v vector
#define fo(i, c) for (int i = 0; i != c; i++)
#define fos(i, s, c) for (int i = s; i != c; i++)

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	ll n, W, m = 0;
	cin >> n >> W;
	v<ll> w(n), u(n);
	fo(i, n) cin >> w[i] >> u[i];
	v<v<ll>> dp(n, v<ll>(n * 1001, n * 2e9));
	fo(i, n) dp[i][0] = 0;
	dp[0][u[0]] = w[0];
	fos(i, 1, n)
	{
		fo(j, n * 1001) dp[i][j] = dp[i - 1][j];
		fos(j, u[i], n * 1001) dp[i][j] = min(dp[i][j], dp[i - 1][j - u[i]] + w[i]);
	}
	fo(i, n * 1001) if (dp[n - 1][i] <= W) m = i;
	cout << m;
	return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll; 

#define test(t) int t;cin>>t;while(t--)
#define forn(i,n) for(i=0;i<n;i++)
#define rforn(i,n) for(i=n-1;i>=0;i--)
#define all(v) (v).begin(),(v).end()
const int MOD = 1e9+7,MAX = 1e5+5;
ll powN(ll a,ll p)
{
	if(p==0) return 1;
	ll z=powN(a,p/2);
	z=(z*z)%MOD;
	if(p%2) z=(z*a)%MOD;
	return z;
}
vector<bool> is_prime(MAX+1, true);
void Sieve()
{
	is_prime[0] = is_prime[1] = false;
	int i,j;
	for (i = 2; i*i <= MAX; i++) 
	{
    	if (is_prime[i]) 
    	{
        	for (j = i * i; j <= MAX; j += i)
            	is_prime[j] = false;
    	}
	}
}
ll modInv(ll a)
{
	return powN(a,MOD-2);
}


int main()
{
	int n,k;
	cin>>n>>k;
	vi h(n);
	for(int i=0;i<n;i++) cin>>h[i];
	vi dp(n,INT_MAX);
	dp[0]=0;
	for(int i=1;i<n;i++)
	{
		for(int j=1;j<=min(i,k);j++)
		{
			dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]));
		}
	}
	cout<<dp[n-1]<<endl;
}

Measured memory_bytes: 1024
A, B, M = map(int, input().split())

AList = list(map(int, input().split(' ', A)))
BList = list(map(int, input().split(' ', B)))

result = 10 ** 10
DisList = []
for i in range(M):
    tmpList = list(map(int, input().split()))
    if result > AList[tmpList[0] - 1] + BList[tmpList[1] - 1] - tmpList[2]:
        result = AList[tmpList[0] - 1] + BList[tmpList[1] - 1] - tmpList[2]

AList.sort()
BList.sort()

if result > AList[0] + BList[0]:
    result = AList[0] + BList[0]

print(result)


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

int dp[2][110][10010];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
#ifdef LOCAL
	std::ifstream in("in");
	std::cin.rdbuf(in.rdbuf());
#endif

	int N, C;
	cin >> N >> C;
	memset(dp, -1, sizeof dp);
	dp[0][0][0] = 0;
	for(int i = 0; i < N; i++){
		int a, b, c;
		cin >> a >> b >> c;
		for(int j = 0; j <= C; j++){
			for(int k = 0; k <= 10000; k++){
				if(dp[0][j][k] == -1) continue;
				int d = dp[0][j][k];
				dp[1][j][k] = max(dp[1][j][k], d);

				if(j + c <= C){
					int x = max(k + a, d + b), y = min(k + a, d + b);
					dp[1][j + c][x] = max(dp[1][j + c][x], y);
					x = max(k + b, d + a), y = min(k + b, d + a);
					dp[1][j + c][x] = max(dp[1][j + c][x], y);
				}
			}
		}
		memcpy(dp[0], dp[1], sizeof dp[0]);
		memset(dp[1], -1, sizeof dp[1]);
	}

	int ans = 0;
	for(int j = 0; j <= C; j++){
		for(int k = 0; k <= 10000; k++){
			if(dp[0][j][k] != -1){
				ans = max(ans, dp[0][j][k]);
			}
		}
	}
	cout << ans << endl;
}

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

int main() {
   string a[7] = {"SUN","MON","TUE","WED","THU","FRI","SAT"};
   string s;
   cin >> s;
   for(int i = 0; i < 7; i++){
     if(s == a[i]) cout << 7-i << endl;
   }
   return 0;
}


Measured memory_bytes: 3600
N = int(input())
T, A = list(map(int, input().split()))
H = list(map(int,input().split()))

temparature = list(map(lambda x: abs(T - x * 0.006 - A), H))
# print(f"H:{H} temparature:{temparature}", file=sys.stderr)
min_index = 0
min_temp = 0
for i, t in enumerate(temparature):
    if i == 0:
        min_temp = t
    else:
        if min_temp > t:
            min_index = i
            min_temp = t
print(min_index + 1)

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

main(){
	int N;
	cin>>N;
	for(int i=0; i<N; ++i){
		int a[3];
		cin >> a[0] >> a[1] >> a[2];
		
		sort(a, a + 3);
		
		if( a[2]*a[2] == a[1]*a[1] + a[0]*a[0] ){
			puts("YES");
		}else{
			puts("NO");
		}
	}
}



Measured memory_bytes: 2964
#include <iostream>
#include <math.h>
using namespace std;


int main(){
    int W , H, x, y,r;
    cin >> W >> H >> x >> y >> r;
    if(x >= r && x <= W-r && y >= r && y <= H-r){
            cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }


    return 0;
}


Measured memory_bytes: 3116
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(a,b) for(int a=0;a<b;a++)
#define Sort(a) sort(a.begin(),a.end())
 int wari(int a,int b) {
   if(a%b==0)
     return a/b;
   else
     return a/b+1;
 }
 int keta(int a){
  double b=a;
  b=log10(b);
  int c=b;
  return c+1;
 }
 int souwa(int a){
  return a*(a+1)/2;
 }
 int lcm(int a,int b){
  int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return d*e/f;
    }
  int gcm(int a,int b){
      int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return f;
  }
signed main(){
  int a,d=0;
  cin>>a;
  vector<int> b(a),c(a);
  fo(i,a)
    cin>>b[i];
  fo(i,a)
    cin>>c[i];
  for(int i=0;i<a;i++)
    d+=max<int>(0,b[i]-c[i]);
  cout<<d<<endl;
}

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

string word[4]={"dream","dreamer", "erase", "eraser"};

int main(int argc, char const *argv[])
{
    string s;cin>>s;
    for(int i=0;i<4;++i)reverse(word[i].begin(),word[i].end());
    reverse(s.begin(),s.end());
    int idx=0;
    while (true)
    {
        bool can=false;
        for(int i=0;i<4;i++){
            if(s.substr(idx,word[i].size())==word[i]){
                idx+=word[i].size();
                can=true;
            }
        }
        if(!can || idx>s.length()){
            cout << "NO" << endl;
            break;
        }
        if(idx == s.length()){
            cout << "YES" << endl;
            break;
        }
    }
    
    return 0;
}


Measured memory_bytes: 512
/** 
 * THIS IS CFMASTER'S CODE !
 * HACK IT IF YOU CAN !
**/
#include <bits/stdc++.h>

using namespace std;

const int MAX = 10000;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int a, b;
  cin >> a >> b;
  for (int i = 1; i <= MAX; i++) {
    if (i * 8 / 100 == a && i * 10 / 100 == b) {
      cout << i << '\n';
      return 0;
    }
  }
  cout << -1 << '\n';
  return 0;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

const (
	initialBufSize = 10000
	maxBufSize     = 10000000
)

var (
	sc = func() *bufio.Scanner {
		sc := bufio.NewScanner(os.Stdin)
		buf := make([]byte, initialBufSize)
		sc.Buffer(buf, maxBufSize)
		sc.Split(bufio.ScanWords)
		return sc
	}()
)

func nextString() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func nextFloat() float64 {
	sc.Scan()
	f, e := strconv.ParseFloat(sc.Text(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func main() {
	n := nextInt()
	a := make([]int, n)
	count := make(map[int]int)
	for i := 0; i < n; i++ {
		a[i] = nextInt()
		count[a[i]]++
	}

	combs := make(map[int]int)
	sum := 0
	for k, v := range count {
		comb := v * (v - 1) / 2
		combs[k] = comb
		sum += comb
	}

	for i := 0; i < n; i++ {
		ans := sum - combs[a[i]]
		c := count[a[i]] - 1
		ans += c * (c - 1) / 2
		fmt.Println(ans)
	}
}


Measured memory_bytes: 23040
import           Control.Applicative
import           Data.List.Split

main :: IO ()
main = do
  [h, w] <- map read.words <$> getLine :: IO [Int]
  _ <- getLine
  xs <- map read.words <$> getLine
  putStr.unlines.map(unwords.map show) $ solve h w xs

solve :: Int -> Int -> [Int] -> [[Int]]
solve h w xs = go.chunksOf w.concat $ zipWith replicate xs [1..]
  where
    go (xs:ys:xss) = xs:reverse ys:go xss
    go xss = xss


Measured memory_bytes: 2428
package main

import (
	"fmt"
	"strconv"
)

func main() {
	var a, b string
	var in int
	fmt.Scanf("%s %s", &a, &b)
	in, _ = strconv.Atoi(a + b)
	for i := 1; i <= 350; i++ {
		if i*i == in {
			fmt.Println("Yes")
			return
		}
	}
	fmt.Println("No")

}


Measured memory_bytes: 512
#include <iostream>
#include <memory.h>
using namespace std;
#define ll long long
#define all(x) x.begin(),x.end()

int const N = 200001;
int n, m, x, c[20], g[20][20], cur[20];

int main(){
    scanf("%d%d%d", &n, &m, &x);
    for(int i = 0; i<n; ++i){
        scanf("%d", c+i);
        for(int j = 0; j<m; ++j){
            scanf("%d", &g[i][j]);
        }
    }
    int an = 1e9, f = 0;
    for(int i = 0; i<=1<<n; ++i){
       memset(cur, 0, sizeof cur);
       int sm = 0, tot = 0; 
       for(int j = 0; j<n; ++j){
         if(i & (1 << j)){
            sm += c[j];
            for(int k = 0; k<m; ++k){
                cur[k] += g[j][k];
            }
         }
       }
       for(int k = 0; k<m; ++k){
         if(cur[k] >= x)++tot;
       }
       if(tot == m)an = min(sm, an), f = 1;
    }
    if(!f)an = -1;
    printf("%d\n", an);
}


Measured memory_bytes: 3844
#include<iostream>
#include<algorithm>
#include<map>
#include<cmath>
#include<vector>
#include<iomanip>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
char a[9][9];
signed main() {
	ll h, w, cnt = 0;
	cin >> h >> w;
	rep(i, h) { rep(j, w)cin >> a[i][j]; }
	rep(i, h) {
		rep(j, w) {
			if (a[i][j] == '#')cnt++;
		}
	}
	if (cnt == h + w - 1)puts("Possible");
	else puts("Impossible");
	getchar(); getchar(); return 0;
}

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

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ll          long long
#define pb          push_back
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define rs(v,n)     v.resize(n)
#define hell        1000000007
#define peak        9123372036854775807
#define pii         acos(-1)
#define clr(a,x)    memset(a,x,sizeof(a))
#define ios         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ordered_set tree<ll int, null_type,less<ll int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
template<class x,class y> x sum(x a,y b){return a+b;}
template<class x,class y> x mul(x a,y b){return a*b;}
template<class x,class y> x sub(x a,y b){return a-b;}
template<class x,class y> x divi(x a,y b){return a/b;}

template<class x,class y>
istream &operator>>(istream &in,pair<x,y> &p) 
{ 
    in>>p.F>>p.S;
    return in;
}
template<class x>
istream &operator>>(istream &in,vector<x> &v) 
{
    for(auto& i:v)
        in>>i;
    return in;
}
template<class x,class y>
ostream &operator<<(ostream &out,pair<x,y> &p) 
{ 
    out<<"("<<p.F<<","<<p.S<<") ";
    return out; 
}
template<class x>
ostream &operator<<(ostream &out,vector<x> &v) 
{ 
    out<<v.size()<<endl;
    for(auto i:v)
        out<<i<<" ";
    out<<endl;
    return out; 
}
#define N  1000005

int main()
{
    ios;
    ll tt=1;
    // cin>>tt;
    while(tt--)
    {
        ll i,j,k,l,m,n;
        cin>>n>>k;
        ll w[103],v[104];
        for(i=1;i<=n;i++)
        {
            cin>>w[i]>>v[i];
        }
        ll dp[100005];
        clr(dp,-hell);
        dp[0]=0;
        for(i=1;i<=n;i++)
        {
            for(j=k;j>=0;j--)
            {
                if(j+w[i]>k)
                    continue;
                dp[j+w[i]]=max(dp[j+w[i]],dp[j]+v[i]);
            }
        }
        ll ans=0;
        for(i=0;i<=k;i++)
        {
            ans=max(ans,dp[i]);
        }
        cout<<ans;
    }
    return 0;
}

Measured memory_bytes: 1024
n = int(input())
datas = input().split(' ')
datas = [int(x) for x in datas if x != '1']

if 0 in datas:
    print(0)
else:
    sums = 1
    for data in datas:
        d = int(data)
        sums *= d
        if sums > 1000000000000000000:
            sums = -1
            break
    print(sums)

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

int N;
double x[8];
double y[8];
bool used[8];

double dist(int n, int p) {
	if (n == N) {
		return 0;
	}

	double res = 0;
	for (int i = 0; i < N; ++i) {
		if (used[i]) {
			continue;
		}

		used[i] = true;
		res += sqrt((x[i] - x[p]) * (x[i] - x[p]) + (y[i] - y[p]) * (y[i] - y[p]));
		used[i] = false;
	}

	return res;
}

int main() {
	cin >> N;
	for (int i = 0; i < N; ++i) {
		cin >> x[i] >> y[i];
	}

	double res = 0;
	for (int i = 0; i < N; ++i) {
		used[i] = true;
		res += dist(N - 1, i);
		used[i] = false;
	}

	cout << setprecision(16) << res / N;

	return 0;
}




Measured memory_bytes: 256
n,x=map(int,input().split())
pos=list(map(int,input().split()))
pos2=[abs(p-x) for p in pos]
def make_divisor_list(num):
    if num < 1:
        return []
    elif num == 1:
        return [1]
    else:
        divisor_list = []
        divisor_list.append(1)
        for i in range(2, num // 2 + 1):
            if num % i == 0:
                divisor_list.append(i)
        divisor_list.append(num)
 
        return divisor_list

if n==1: ans=pos2[0]
else:
    minpos= min(pos2)
    divs=make_divisor_list(minpos)[::-1]
    if divs[0]==1:ans=1
    else:
        for j in divs:
            if all(x%j==0 for x in pos2):
                ans=j
                break
print(ans)

Measured memory_bytes: 14480
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>
#include <set>
#include <bitset>
#include <cmath>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define FI first
#define SE second
#define MA(i,j) make_pair(i,j)
#define PA pair<int,int>
#define PB push_back
#define PQ priority_queue<int>
#define PGQ priority_queue<int,vector<int>,greater<int> >
#define VE vector<int>
#define VP vector<PA>
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
using namespace std;
//
const int MOD=1e9+7;
const int INF=1e9+7;
const double PI=3.141592653589793238462643383279;
//
int main(){
  int A,B;
  cin>>A>>B;
  if(A*B%2){
    cout<<"Odd"<<endl;
  }else{
    cout<<"Even"<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <stdlib.h>
#include <cmath>
#include <cstdio>
#include <cstdint>
#include <string>
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
using namespace std;
using ll = long long;

int main(){
  int N;
  cin >> N;
  int X=-1;
  for(int i=(int)(N/1.08);i<(int)(N/1.08)+3;i++){
    if((int)(i*1.08)==N){
      X=i;
      break;
    }
  }

  if(X==-1) cout << ":(" << endl;
  else cout << X << endl;

  return 0;
}


Measured memory_bytes: 256
#[allow(unused_imports)]
use proconio::marker::{Bytes, Chars, Usize1};
use proconio::{fastout, input};
#[fastout]
fn main() {
    input! {
        n: usize,
        k: usize,
        r: usize,
        s: usize,
        p: usize,
        t: Chars,
    }
    let mut ans = 0;
    let mut a = vec![false; n];
    for i in 0..n {
        if i < k {
            ans += score(t[i], r, s, p);
            continue;
        }
        if t[i] != t[i - k] {
            ans += score(t[i], r, s, p);
        } else {
            // t[i] == t[i - k]
            if a[i - k] == true {
                ans += score(t[i], r, s, p);
            } else {
                a[i] = true;
            }
        }
    }
    println!("{}", ans);
}
fn score(a: char, r: usize, s: usize, p: usize) -> usize {
    match a {
        'r' => p,
        's' => r,
        'p' => s,
        _ => 0,
    }
}


Measured memory_bytes: 2556
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
int n, c[5]; string s;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s;
		if (s[0] == 'M') c[0]++;
		if (s[0] == 'A') c[1]++;
		if (s[0] == 'R') c[2]++;
		if (s[0] == 'C') c[3]++;
		if (s[0] == 'H') c[4]++;
	}
	long long ret = 0;
	for (int i = 0; i < 5; i++) {
		for (int j = i + 1; j < 5; j++) {
			for (int k = j + 1; k < 5; k++) {
				ret += 1LL * c[i] * c[j] * c[k];
			}
		}
	}
	cout << ret << endl;
	return 0;
}

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

namespace abc153
{
    class Program
    {
        static void Main(string[] args)
        {
            if (File.Exists("input.txt"))
            {
                Console.SetIn(new StreamReader("input.txt"));
            }
			solve_abc153D();
        }

        public static void solve_abc153D()
        {
            long h = Convert.ToInt64(Console.ReadLine());
            long k = 1;
            long cnt = 0;
            while (h > 0)
            {
                h /= 2;
                cnt += k;
                k *= 2;
            }
            Console.WriteLine(cnt);
        }

        public static void solve_abc153C()
        {
            int[] nk = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int n = nk[0];
            int k = nk[1];
            int[] h = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

            Array.Sort(h, (a, b) => b.CompareTo(a));

            long cnt = 0;
            for (int i = k; i < n; i++)
            {
                cnt += h[i];
            }
            Console.WriteLine(cnt);
        }

        public static void solve_abc153B()
        {
            int[] hn = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int h = hn[0];
            int n = hn[1];
            int[] a = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            for (int i = 0; i < n; i++)
            {
                h -= a[i];
            }
            if (h <= 0)
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }
        }

        public static void solve_abc153A()
        {
            int[] ha =  Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            Console.WriteLine((ha[0] + ha[1] - 1) / ha[1]);
        }
    }
}


Measured memory_bytes: 11220
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <string>
#include <queue>
#include <numeric>
#include <ctype.h>
#include <limits>
#include <iomanip>

#define rep(i,n) for (int i = 0; i < n; i++)
#define all(x) (x).begin(),(x).end()
using namespace std;

typedef long long ll;

int main()
{
	int r;
	cin >> r;
	cout << r * r;
	return 0;
}

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

int main() {
  int N, currentValue[200];

  cin >> N;
  
  for (int i = 0; i < N; i++) {
    cin >> currentValue[i];
  }

  bool isOdd = false;
  int total = 0;

  while (true) {
    for (int i = 0; i < N; i++) {
      int current = currentValue[i] % 2;
      currentValue[i] /= 2;
      if (current != 0) isOdd = true;
    }
    
    if (isOdd) break;
     
    total++;
  }
  
  cout << total << endl;
}


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

public class Main{

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Point a = new Point();
        Point b = new Point();
        a.x = 0;
        a.y = 0;
        b.x = 100;
        b.y = 0;

        System.out.println(a.x + " " + a.y);
        koch(n, a, b);
        System.out.println(b.x + " " + b.y);
     }

    public static void koch(int n, Point a, Point b){
        if(n == 0) return;
        Point s = new Point();
        Point t = new Point();
        Point u = new Point();
        double th = (Math.PI / 180) * 60;

        s.x = (2.0 * a.x + 1.0 * b.x) / 3.0;
        s.y = (2.0 * a.y + 1.0 * b.y) / 3.0;
        t.x = (1.0 * a.x + 2.0 * b.x) / 3.0;
        t.y = (1.0 * a.y + 2.0 * b.y) / 3.0;
        u.x = (t.x - s.x) * Math.cos(th) - (t.y - s.y) * Math.sin(th) + s.x;
        u.y = (t.x - s.x) * Math.sin(th) + (t.y - s.y) * Math.cos(th) + s.y;

        koch(n - 1, a, s);
        System.out.println(s.x + " " + s.y);
        koch(n - 1, s, u);
        System.out.println(u.x + " " + u.y);
        koch(n - 1, u, t);
        System.out.println(t.x + " " + t.y);
        koch(n - 1, t, b);
    }

}


class Point{
    double x, y;
}

Measured memory_bytes: 30340