akhauriyash/Code-Regression huggingface dataset:
//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <string>
#include <set>
#include <stack>
#include <sstream>
#include <list>
//#include <array>
#include <vector>
#include <queue>
#include <map>
#include <memory>
#include <iterator>
#include <climits>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef unsigned int UINT;
typedef unsigned long long ull;
typedef pair<int, int> pdi;
typedef pair<ll, int> pli;

int const maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;
inline int lc(int x)  {return x << 1;}
inline int rc(int x)  {return x << 1 | 1;}

int a[] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51
};

int main(void) {
    FAST_IO;
    
    int k;
    cin >> k;
    cout << a[k - 1] << endl;
    
    return 0;
}

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

int main(){
	int h, w, n;
	cin >> h >> w >> n;
	vector<int> a(n);
	rep(i, n) cin >> a.at(i);
	vector<vector<int>> ans(h, vector<int>(w));
	int c = 0;
	int x= 0, y = 0;
	bool flag = false;
	for(; y < h; y++){
		while(1){
			if(a.at(c) == 0){
				c++;
			}
			ans.at(y).at(x) = c+1;
			a.at(c)--;
			if(flag == false){
				if(x == w-1){
					flag = true;
					break;
				}else{
					x++;
				}
			}else{
				if(x == 0){
					flag = false;
					break;
				}else{
					x--;
				}
			}
		}
	}
	rep(i, h){
		rep(j, w){
			if(j != w-1) cout << ans.at(i).at(j) << " ";
			else cout << ans.at(i).at(j) << endl;
		}
	}
	
	return 0;
}

Measured memory_bytes: 384
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

// c++11
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>

#define mp make_pair
#define mt make_tuple
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
template <class T>
using max_priority_queue = priority_queue<T>;
template <class T>
using min_priority_queue = priority_queue<T, std::vector<T>, std::greater<T>>;

const int INF = 1 << 29;
const ll LL_INF = 1LL << 60;
const double EPS = 1e-9;
const ll MOD = 1000000007;

const int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};
int N, X;
vector<int> L;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> X;
    L.resize(N);
    for (auto &val : L)
    {
        cin >> val;
    }
    int d = 0;
    int cnt = 0;
    for (int i = 0; i < N; i++)
    {
        if (d <= X)
        {
            cnt++;
        }
        d = d + L[i];
    }
    if (d <= X)
    {
        cnt++;
    }
    cout << cnt << endl;
    return 0;
}


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

int main() {
    ll X; cin >> X;
    double cur = 100;
    int i = 0;
    while (cur < X) {
        cur *= 1.01;
        cur = (ll)cur;
        i++;
    }
    cout << i << endl;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
typedef long long ll;


int main(){
  string S;
  cin >> S;
  vector<bool> alph(26,false);
  if(S.size() < 26){
    rep(i,S.size()) alph[S[i] - 'a'] = true;
    rep(i,26){
      if(alph[i] == false){
        cout << S << (char)(i+'a') << endl;
        return 0;
      }
    }
  }
  vector<string> ans;
  for(int i = S.size()-1; i >= 0; i--){
    for(int j = i-1; j >= 0; j--){
      if(S[i] > S[j]){
        char tmp = S[i];
        S[i] = S[j];
        S[j] = tmp;
        ans.push_back(S.substr(0,j+1));
        S[j] = S[i];
        S[i] = tmp;
      }
    }
  }
  if(ans.size() == 0){
    cout << -1 << endl;
    return 0;
  }else{
    sort(all(ans));
    cout << ans[0] << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n;
string s[100007];
map<string,int>p;
long long ans;
int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; i++) {
		cin>>s[i];
		sort(s[i].begin(),s[i].end());
		ans+=p[s[i]];
		p[s[i]]++;
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 18176
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <sstream>
using namespace std;

long long aaaaa(long long pat, int k)
{
	long long a = 2;
	long long b = 1;
	long long c;  
	for (int i = 0; i < k - 2; i++) {
		a %= 1000000007;
      	c = a;
		a += b;
		b = c;
	}
	pat *= a;
//cout << a << " " << pat << endl;
	pat %= 1000000007;
	return pat;
}

int main()
{
	int n, m;
	cin >> n >> m;
	vector<int> x(m);
	if (m > 0) {
		for (int i = 0; i < m; i++) {
			cin >> x[i];
			x[i]--;
		}
	}
	long long pat = 1;
	int z = 0;
	int k = 0;
	int j = 0;
	for (int i = 0; i < n; i++) {
		if (j < m && i == x[j]) {
			if (k > 1) {
				pat = aaaaa(pat, k);
			}
			k = -1;
			z++;
			if (z == 2) {
				pat = 0;
				break;
			}
			j++;
		}
		else {
			z = 0;
			k++;
		}
	}

	if (k > 1) {
		pat = aaaaa(pat, k);
	}

	cout << pat << endl;
	return(0);
}




Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int n, m, k;
int main()
{
	scanf("%d%d", &m, &k);
	if(m == 0)
	{
		if(k == 0)
			puts("0 0");
		else
			puts("-1");
		return 0;
	}
	if(m == 1)
	{
		if(k == 0)
			puts("0 0 1 1");
		else
			puts("-1");
		return 0;
	}
	n = (1 << m);
	if(k >= n)
	{
		puts("-1");
		return 0;
	}
	for(int i = 0; i < n; ++i)
		if(i != k)
			printf("%d ", i);
	printf("%d ", k);
	for(int i = n - 1; ~i; --i)
		if(i != k)
			printf("%d ", i);
	printf("%d\n", k);
	return 0;
}

Measured memory_bytes: 1792
import numpy as np
import sys
input = sys.stdin.readline


def main():
    n, s = map(int, input().split())
    A = np.array([int(i) for i in input().split()])

    MOD = 998244353

    dp = np.zeros(s + 1, dtype="int32")
    dp[0] = 1

    for a in A:
        p = (dp * 2) % MOD
        p %= MOD
        p[a:] += dp[:-a]
        dp = p % MOD

    print(dp[s])


if __name__ == '__main__':
    main()

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

using namespace std;

int a,b,c,d,e,f;

bool water[3010];
bool sugar[3010];

double getNoudo(int w,int s)
{
    return 100.0*s/(w+s);
}

int main(void)
{
    cin>>a>>b>>c>>d>>e>>f;
    for(int i = 0;i < 100;i++)
    {
        for(int j = 0;j < 100;j++)
        {
            int x = 100*a*i+100*b*j;
            if(x > f)
                continue;
            water[x] = true;
        }
    }

    for(int i = 0;i < 100;i++)
    {
        for(int j = 0;j < 100;j++)
        {
            int y = c*i+d*j;
            if(y > f)
                continue;
            sugar[y] = true;
        }
    }

    double mc = 0.0;
    int mw = a*100,ms = 0;
    for(int w = 100;w < 3000;w+= 100) {
        for(int s = 0;s < 3000 - w;s++) {
            if(water[w] == false or sugar[s] == false)
                continue;
            if(w+s > f)
                break;
            if(e*(w/100) < s)
                break;

            double temp = getNoudo(w,s);
            if(temp > mc)
            {
                mc = temp;
                mw = w;
                ms = s;
            }
        }
    }

    cout<<mw+ms<<" "<<ms<<endl;

    return 0;
}


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

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

    long long int n;

    while (std::cin >> n, n) {
        std::array<long long int, 7> arr{{}};
        int age;
        for (; n--;) {
            std::cin >> age;
            age = (age > 69 ? 60 : age);
            ++arr[age / 10];
        }

        for (const auto& cnt : arr) {
            std::cout << cnt << std::endl;
        }
    }

    return 0;
}

Measured memory_bytes: 1200
#include <bits/stdc++.h>
using namespace std;
char str[100001];
int main()
{
    gets(str);
   for(int i=1;i<=strlen(str);i++)
   {
       if(str[i-1]==',') str[i-1]=' ';
   }
   puts(str);
    cout<<endl;    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define Dim 1<<14
using namespace std;
ifstream f("A.in");
typedef long long ll;
ll N,M,X,A[15],P[15],x,ans=-1,cost;
ll dp[Dim],L[Dim][15];
bool viz[15];
vector <ll> V[15];
vector < ll > dq;


int main()
{
    cin>>N>>M>>X;
    for(int i=0;i<N;i++)
    {
        cin>>P[i];
        V[i].push_back(0);
        for(int j=1;j<=M;j++)
        {
            cin>>x;
            V[i].push_back(x);
        }
    }
    for(int i=0;i<(1<<N);i++)
    {
        int lg=log2(i)+1;
        cost=0;
        for(int k=0;k<=lg;k++)
        if( ( i & (1<<k) ) > 0 )
        {
            cost+=P[k];
            for(int j=1;j<=M;j++)
            L[i][j]+=V[k][j];
        }

        bool stop=0;
        for(int j=1;j<=M&&stop==0;j++)
        if(L[i][j]<X) stop=1;

        if(stop==0)
        {
            if(ans==-1) ans=cost;
            else
            if(cost<ans) ans=cost;
        }
    }
   cout<<ans;


    return 0;
}


Measured memory_bytes: 4304
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
using namespace std;
typedef  long long int lint;
typedef pair<int, int> P;
typedef pair<lint, lint> LLP;
typedef pair<char, char>CP;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define llower(v,hoge) *lower_bound(v.begin(), v.end(), hoge)
#define lupper(v,hoge) *upper_bound(v.begin(), v.end(), hoge)
/*
vector<char>al(26);
al = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
vector<char>AL(26);
AL = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
vector<char>NUM(10);
	NUM = { '0','1','2' ,'3' ,'4' ,'5' ,'6' ,'7' ,'8' ,'9' };
*/



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

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(char a,char b)
{
return a>b;
}
int main()
{
string s,t;
cin>>s>>t;
sort(s.begin(),s.end());
sort(t.begin(),t.end(),cmp);
if(s<t)
cout<<"Yes";
else
cout<<"No";
return 0;
}

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

int main(){
  int sx, sy, tx, ty;
  cin>>sx>>sy>>tx>>ty;
  int x = tx-sx, y = ty-sy;
  for(int i=0;i<x;i++) cout<<"R";
  for(int i=0;i<y;i++) cout<<"U";
  for(int i=0;i<x;i++) cout<<"L";
  for(int i=0;i<y;i++) cout<<"D";
  cout<<"D";
  for(int i=0;i<x+1;i++) cout<<"R";
  for(int i=0;i<y+1;i++) cout<<"U";
  cout<<"LU";
  for(int i=0;i<x+1;i++) cout<<"L";
  for(int i=0;i<y+1;i++) cout<<"D";
  cout<<"R"<<endl;
  return 0;
}


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

int main() {
  int n;
  cin >> n;
  string s,t;
  cin >> s;
  cin >> t;
  for(int i=0;i<n;i++){
    if(s.substr(i)==t.erase(n-i)){
      cout << n+i << endl;
      return 0;
    }
  }
  cout << 2*n << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#define MAX 100
#define INFTY 1<<21
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n,M[MAX][MAX];

int prim(){
  int u,minv;
  int d[MAX],p[MAX],color[MAX];
  int i;
  int sum;
  for(i=0;i<n;i++){
    d[i]=INFTY;
    p[i]=-1;
    color[i]=WHITE;
  }
  d[0]=0;
  while(1){
    minv=INFTY;
    u=-1;
    for(i=0;i<n;i++){
      if(minv>d[i]&&color[i]!=BLACK){
	u=i;
	minv=d[i];
      }
    }
    if(u==-1) break;
    color[u]=BLACK;
    for(i=0;i<n;i++){
      if(color[i]!=BLACK&&M[u][i]!=INFTY){
	if(d[i]>M[u][i]){
	  d[i]=M[u][i];
	  p[i]=u;
	  color[i]=GRAY;
	}
      }
    }
  }
  sum=0;
  for(i=0;i<n;i++){
    if(p[i]!=-1) sum+=M[i][p[i]];
  }
  return sum;
}

int main(void){
  int i,j,e;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      scanf("%d",&e);
      M[i][j]=(e==-1)?INFTY:e;
    }
  }
  printf("%d",prim());
  printf("\n");
  return 0;
}



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


template <typename T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &v){
    if(!v.empty()) {
        out << '[';
        std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
        out << "\b\b]";
    }
    return out;
}

template <typename T1, typename T2>
std::ostream &operator<<(std::ostream &out, const std::pair<T1, T2> &p) {
    out << "[" << p.first << ", " << p.second << "]";
    return out;
}
//---------


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    int ans = k * pow((k-1), n-1);
    cout << ans << endl;
    return 0;
    
    
}

Measured memory_bytes: 256
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    return arr

z = factorization(int(input()))
i = 1
ans = 0
flag = True
while flag:
    flag2 = False
    for j in range(len(z)):
        if z[j][1] >= i:
            z[j][1] -= i
            ans += 1
            flag2 = True

    i += 1
    if flag2 == False: flag = False
print(ans)


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

using namespace std;


int main() {
	char a, b;
	cin >> a >> b;
	if(a == 'H' && b == 'D')
		cout << "D";
	else if(a == 'H' && b == 'H')
		cout << "H";
	else if(a == 'D' && b == 'D')
		cout << "H";
	else if(a == 'D' && b == 'H')
		cout << "D";
	return 0;
}


Measured memory_bytes: 3532
while True:
    s1 = input()
    if s1 == ".":
        break
    s2 = input().split("\"")
    s1 = s1.split("\"")
    if len(s1) != len(s2):
        print("DIFFERENT")
    else:
        fin = False
        count = 0
        for i in range(len(s1)):
            if i%2 == 0:
                if s1[i] != s2[i]:
                    print("DIFFERENT")
                    fin = True
                    break
            else:
                if s1[i] != s2[i]:
                    count += 1
                    if count > 1:
                        print("DIFFERENT")
                        fin = True
                        break
        if not fin:
            if count == 1:
                print("CLOSE")
            elif count == 0:
                print("IDENTICAL")



Measured memory_bytes: 5580
//*******Abhijit Burman***********//
//Jalpaiguri Government Engineering College//

#include<bits/stdc++.h>
using namespace std;
#define ll long long int

#define pb push_back
#define mk make_pair
#define MAXX (1000000000000000000+7)
#define fio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)


ll dp[100100][110];

ll knapsack(ll a[], ll b[],ll wt ,ll index)
{
    //cout<<wt<<endl;
    if(index <0)
    {
        return 0;
    }
    if(dp[wt][index]!=-1)
    {
        return dp[wt][index];
    }
    else
    {
        if(wt-a[index]<0)
        {
            dp[wt][index] = knapsack(a,b,wt,index-1);
        }
        else
            dp[wt][index] = max(b[index]+knapsack(a,b,wt-a[index],index-1),knapsack(a,b,wt,index-1));
        return dp[wt][index];
    }

}
void solve(ll t)
{
	ll n,w;
	cin>>n>>w;
	ll a[n],b[n];
    memset(dp,-1,sizeof(dp));
	for(int i=0;i<n;i++)
    {
        cin>>a[i]>>b[i];
    }
    ll ans = knapsack(a,b,w,n-1);

    cout<<ans<<endl;
}


int main()
{
	ll t=1;
	//cin>>t;
	while(t--)
	{
		solve(t);
	}
	return 0;
}


Measured memory_bytes: 86272
n, x, y = map(int, input().split())
result = [0] * n
for i in range(1,n):
    for j in range(i+1, n+1):
        result[min([(j - i), (abs(i - x) + 1 + abs(j - y))])] += 1

for i in range(1,n):
    print(result[i])



Measured memory_bytes: 3444
#include<stdio.h>
#include<string.h>
int main(void)
{
	int a,f,k,i,j,z=0;
	char s[1000],d[1000],h[1000];
	scanf("%s",s);
	a=strlen(s);
	scanf("%s",d);
	f=strlen(d);
	strcpy(h,s);
	strcat(s,h);
	k=strlen(s);
	/*for(i=0;i<=k;i++)
		printf("%c",s[i]);*/
	for(i=0;i<=k;i++){
		for(j=0;j<=f;j++){
			if(s[j+i]!=d[j])
				break;
		}
		//printf("j = %d %c %c\n",j,s[j+i-1],s[j+i]);
		if(j==f){
			z=1;
			break;
		}
	}
	if(z==1)
		printf("Yes\n");
	else
		printf("No\n");
	return 0;
}

Measured memory_bytes: 2756
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
#define inf (int)(1e9+7)
#define INF (ll)(1e18)
#define abs(x) (x >= 0 ? x : -(x))
#define ceil(a, b) a / b + !!(a % b)
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }






const int mod = 1000000007;

struct mint {
    ll x;
    mint (ll x = 0) : x(x % mod) {}
    mint& operator += (const mint a) { // コンストラクタの、modで割った余りがくる
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator -= (const mint a) {
        if ((x += -a.x + mod) >= mod) x -= mod;
        return *this;
    }
    mint& operator *= (const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator + (const mint a) const {
        mint res(*this);
        return res += a; // ?
    }
    mint operator - (const mint a) const {
        mint res(*this);
        return res -= a;
    }
    mint operator * (const mint a) const {
        mint res(*this);
        return res *= a;
    }
    mint pow(ll t) const { // mint(a).pow(t) tは余りとったりしたらあかん
        if (t == 0) return 1;
        mint a = pow(t >> 1); // 再帰
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }
    
    // 逆元
    mint inv() const {
        return pow(mod - 2);
    }
    mint& operator /= (const mint a) { // invを利用
        return (*this) *= a.inv();
    }
    mint operator / (const mint a) const {
        mint res(*this);
        return res /= a;
    }
    friend ostream &operator<<(ostream &s, mint a) { return s << a.x; }
};



mint P[70];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    P[0] = 1;
    rep3(i, 1, 70) P[i] = P[i - 1] * 2;
    
    ll n;
    cin >> n;
    
    vector<mint> a(n);
    vector<ll> table(70);
    
    rep(i, n) {
        ll tmp;
        cin >> tmp;
        a[i] = tmp;
        int keta = 0;
        while (tmp) {
            if (tmp % 2) table[keta]++;
            keta++;
            tmp /= 2;
        }
    }
    
    mint ans = 0;
    rep(i, n) ans += a[i];
    ans *= (n - 1);
    
    rep(i, 70) {
        if (table[i] >= 2) ans -= P[i] * table[i] * (table[i] - 1);
    }
    
    cout << ans << endl;
}




Measured memory_bytes: 2560
int debug = 0;
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007;
#define VFOR(x,a,b) for(int x=(a);x<((a)+(b));x++)
ll table[2000010],tablepow[2000010],btable[2000010];
void tableCal();
ll Cmb(ll a, ll b);
ll modpow(ll a, ll p);
int main(){
  ll r1,r2,c1,c2,ans=0;
  cin >> r1 >> c1 >> r2 >> c2;
  tableCal();
  /*
  for(ll i = r1; i <= r2; i++){for(int j = c1; j <= c2; j++){
    ans += Cmb(i+j,i);
    ans = ans % MOD;
  }}
  */
  for(ll c = c1; c <= c2; c++){
    ll tmp = 0, tmp2 = 0;
    tmp = (((table[r2+c+1]*tablepow[r2])%MOD)*tablepow[c+1])%MOD;
    tmp2 = (((table[r1+c]*tablepow[c+1])%MOD)*tablepow[r1-1])%MOD;
    tmp2 = MOD - tmp2;
    tmp += tmp2;
    ans += tmp;
    ans %= MOD;
  }
  cout << ans;
  return 0;
}
ll Cmb(ll a, ll b){
  ll X,Y;
  /*
  X = table[a]; Y = table[b]*table[a-b] % MOD;
  Y = modpow(Y,MOD-2);
  Y *= X;
  Y = Y % MOD;
  */
  X = table[a]; Y = tablepow[b]*tablepow[a-b] % MOD;
  Y *= X;
  Y = Y %  MOD;
  return Y;
}
void tableCal(){
  ll tmp = 1,tmp2;
  table[0] = 1;
  tablepow[0] = 1;
  VFOR(i,1,2000005){
    tmp *= i;
    tmp = tmp % MOD;
    table[i] = tmp;
    tmp2 = modpow(tmp,MOD-2) % MOD;
    tablepow[i] = tmp2;
  }
}
ll modpow(ll a, ll p){
  if(p==0) return 1;
  if(p % 2 == 0) { ll tmp= modpow(a,p/2); tmp *= tmp; tmp = tmp % MOD; return tmp;}
  else {ll tmp = a*modpow(a,p-1); tmp = tmp % MOD; return tmp;}
}

Measured memory_bytes: 32768
N,x=map(int,input().split())
a=list(map(int,input().split()))
a=sorted(a)
cnt=0
for i in range(N):
    if sum(a)==x:
        cnt=N
    elif sum(a)>x:
        if x>=a[i]:
            x-=a[i]
            cnt+=1
        else:
            break
    else:
        cnt=N-1

print(cnt)

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

#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = (n)-1; i >= 0; i--)
#define rep1(i,n) for(int i = 1; i <= (n); i++)
#define rrep1(i,n) for(int i = (n); i > 0; i--)

#define ll long long
#define pi pair<int, int>
#define pll pair<ll, ll>

#define MOD 1000000007
#define INF 1000000000000000LL

using namespace std;

int main(){
  string s;cin>>s;
  map<char,int>m;
  rep(i, s.size())m[s[i]]++;
  if(m.size()>1)cout<<"Yes";
  else cout<<"No";

  return 0;
}

Measured memory_bytes: 256
#pragma region template
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const long long MOD = 998244353, MAX = 1e18, larg = 1e5, INF = -1e18;
long long A, B, C, D, E, F, G, H, I, J, K, L, N, M, O, P, Q, R, S, T, U, V, W, x, y, z;
long long max_value = INF, max_index = -1;
long long min_value = MAX, min_index = -1;
typedef long long ll;

template <std::int_fast64_t Modulus>
class modint
{
	using u64 = std::int_fast64_t;

public:
	u64 a;
	constexpr modint(const u64 x = 0) noexcept : a(x% Modulus) {}
	constexpr u64& value() noexcept { return a; }
	constexpr const u64& value() const noexcept { return a; }
	constexpr modint operator+(const modint rhs) const noexcept
	{
		return modint(*this) += rhs;
	}
	constexpr modint operator-(const modint rhs) const noexcept
	{
		return modint(*this) -= rhs;
	}
	constexpr modint operator*(const modint rhs) const noexcept
	{
		return modint(*this) *= rhs;
	}
	constexpr modint operator/(const modint rhs) const noexcept
	{
		return modint(*this) /= rhs;
	}
	constexpr modint& operator+=(const modint rhs) noexcept
	{
		a += rhs.a;
		if (a >= Modulus)
		{
			a -= Modulus;
		}
		return *this;
	}
	constexpr modint& operator-=(const modint rhs) noexcept
	{
		if (a < rhs.a)
		{
			a += Modulus;
		}
		a -= rhs.a;
		return *this;
	}
	constexpr modint& operator*=(const modint rhs) noexcept
	{
		a = a * rhs.a % Modulus;
		return *this;
	}
	constexpr modint& operator/=(modint rhs) noexcept
	{
		u64 exp = Modulus - 2;
		while (exp)
		{
			if (exp % 2)
			{
				*this *= rhs;
			}
			rhs *= rhs;
			exp /= 2;
		}
		return *this;
	}
};
typedef modint<MOD> m;
#pragma endregion

m func[200003];
void funcinit(int N)
{
	func[0] = 1;
	for (int i = 1; i <= N; i++)
	{
		func[i] = func[i - 1] * i;
	}
}
m comb(m n, m r)
{
	if (n.a <= 0 || n.a < r.a)
	{
		return 0;
	}
	return func[n.a] / (func[r.a] * func[(n - r).a]);
}

m calc(m a, ll b) {
	if (b == 0) return 1;
	if (b % 2 == 0) {
		m d = calc(a, b / 2);
		return d * d;
	}
	else {
		return a * calc(a, b - 1);
	}
}
int main() {
	cin >> N >> M >> K;
	m sum = calc(M, N);
	funcinit(N);
	//隣り合うやつが同じ色の組がk組
	for (int k = K+1; k < N; k++) {
		m mul;
		mul.a = M;
		m tmp, tmp2;
		tmp.a = M - 1;
		mul *= calc(tmp, N - k - 1);
		tmp.a = N - 1;
		tmp2.a = k;
		mul *= comb(tmp, k);
		sum -= mul;
	}
	cout << sum.a;
}


Measured memory_bytes: 5144
#!/usr/bin/env python3
# CGL_4_A: Convex Polygon - Convex Hull

from operator import itemgetter


def cross(v1, v2):
    x1, y1 = v1
    x2, y2 = v2
    return x1 * y2 - x2 * y1


def convex_hull(ps):
    ps.sort(key=itemgetter(0))
    ps.sort(key=itemgetter(1))
    p0 = ps[0]
    vs = [(p0, p0)]
    for p in ps[1:]:
        x, y = p
        p1, v1 = vs.pop()
        x1, y1 = p1
        v = (x-x1, y-y1)
        while vs and cross(v1, v) < 0:
            p1, v1 = vs.pop()
            x1, y1 = p1
            v = (x-x1, y-y1)

        vs.append((p1, v1))
        vs.append((p, v))

    for p in reversed(ps[:-1]):
        x, y = p
        p1, v1 = vs.pop()
        x1, y1 = p1
        v = (x-x1, y-y1)
        while vs and cross(v1, v) < 0:
            p1, v1 = vs.pop()
            x1, y1 = p1
            v = (x-x1, y-y1)

        vs.append((p1, v1))
        vs.append((p, v))

    return [p for p, v in vs[:-1]]


def run():
    n = int(input())
    ps = []

    for _ in range(n):
        x, y = [int(i) for i in input().split()]
        ps.append((x, y))

    convex = convex_hull(ps)

    print(len(convex))
    for p in convex:
        print('{} {}'.format(*p))


if __name__ == '__main__':
    run()



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

int main() {
  int a, b, c;
  
  int X;
  int t = 1;
  int f = 0;
  cin >> X;

  for (int i = 0; i < 8; i++) {
    f += X/t%10;
    t = t*10;
  }

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

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  
  int a = N / 1000, b = N / 100 % 10, c = N / 10 % 10, d = N % 10;
  
  if((a == b && b == c) || (b == c && c == d))
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _overload3(_1,_2,_3,_4,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,n) (int i=a;i<n;i++)
#define per(i,a,n,s) (int i=n-1;i>=a;i--)
#define range(...) _overload3(__VA_ARGS__,per,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define vecin(x) for(auto&youso_: (x) ) cin >>  youso_
#define vecout(x) for(auto&youso_: (x) ) cout << youso_ << " " ; cout << endl
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const int inf = 1e9+10;
const int mod = 1e9+7;
const long long llinf = 1e18;
#define _GLIBCXX_DEBUG
// head

int main(){
    int n;
     cin >> n;
     if (n%2==0) { cout << 0.5 << endl; }
     else { cout << (n/2+1)/double(n) << endl; }
}


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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N; cin >> N;
  vector<int> C(N), S(N), F(N);
  rep(i, N-1) cin >> C[i] >> S[i] >> F[i];
  vector<int> ans(N);
  rep(i, N) {
    int t = 0;
    for(int j=i; j<N-1; ++j) {
      int k = max(0.0, ceil((double)(t-S[j])/F[j]));
      t = S[j] + k*F[j];
      t += C[j];
    }
    cout << t << endl;
  }
}

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

int main(){
  int n,m;
  cin >> n >> m;
  vector<int> ans(n,1);
  int mn,mx;
  rep(i,m){
    int l,r;
    cin >> l >> r;
    if( i==0 ){
      mn = l;
      mx = r;
    }else{
      if( mx >= l && mx  <= r && mn <= l ){
        mn = l;
      }else if( mn >= l && mn <= r && mx >= r ){
        mx = r;
      }else if( mn <= l && mx >= r ){
        mn = l;
        mx = r;
      }else if( mn >= l && mx <= r ){
        
      }else{
        cout << 0 << endl;
        return 0;
      }
    }
  }
  
  cout << mx-mn+1 << endl;
    
  return 0;
}


Measured memory_bytes: 640
#include<stdio.h>
int main()
{
 

    int a,b,c;
    

    // スペース区切りの整数の入力
    scanf("%d %d",&b,&c);
  
  
  

  int ans = 0;
  
  switch(b) {
    case 1:
      ans = ans + 300000;
        break;
    case 2:
      ans = ans + 200000;
        break;
    case 3:
        ans = ans + 100000;
        break;
   
        
}
  switch(c) {
    case 1:
      ans = ans + 300000;
        break;
    case 2:
      ans = ans + 200000;
        break;
    case 3:
        ans = ans + 100000;
        break;
  
        
}
  	if(b == 1 && c == 1){
		ans = ans + 400000;
    }
  
  	

    printf("%d",ans);//printf("%c",s[0])//文字一つ分のみを出力

    return 0;
}

Measured memory_bytes: 128
import sys


def input():
    return sys.stdin.readline().rstrip()



def main():
    N = int(input())

    dp = [0] * (N + 1)
    rt = int(N ** 0.5) + 1
    for i in range(1, rt):
        ii = i ** 2
        for j in range(1, i+1):
            iji = ii + j **2 + i * j

            if iji + 1 + i + j > N:
                break
            for k in range(1, j+1):
                case = iji + k**2 + i * k + j * k
                l =6
                if i == j or j == k:
                    l = 3
                    if i == k:
                        l = 1
                if case <= N:
                    dp[case] += l
                else:
                    break

    print(*dp[1:N + 1], sep="\n")


if __name__ == "__main__":
    main()


Measured memory_bytes: 68940
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int N; cin >> N;
    vector<long long> A(N+1), S(N+1);
    map<long long, int> M;
    for (int i = 1; i <= N; i++) cin >> A[i];
    for (int i = 1; i <= N; i++) S[i] = S[i-1] + A[i];
    for (int i = 0; i <= N; i++) M[S[i]]++;
    long long ans = 0;
    for (auto p : M) {
        if (p.second > 1) {
            ans += (long long)p.second * (p.second-1) / 2;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 15872
import java.util.*;
class Main{
public static void main(String[] args){
  Scanner sc=new Scanner(System.in);
  String s=sc.next();
  if(s.equals("Sunny")){
  System.out.println("Cloudy");
  }else if(s.equals("Cloudy")){
  System.out.println("Rainy");
  }else{
  System.out.println("Sunny");
  }
  
}

}

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

char oomozi ( string I ){
  char i;
  char dif = 'A' - 'a';
  i = I.at(0) + dif;
  return i;
}

int main() {
  string a, b, c;
  cin >> a >> b >> c;
  
  cout << oomozi(a) << oomozi(b) << oomozi(c) <<endl;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main(){
    int n,ans=-inf; cin>>n;
    vector<int> f(n,0);
    rep(i,n)rep(j,10){
        int F; cin>>F;
        f[i]^=(F<<(9-j));
    }
    vector<vector<int>> p(n,vector<int>(11,0));
    rep(i,n)rep(j,11){
        cin>>p[i][j];
    }
    rep(i,(1<<10)){
        if(i==0) continue;
        int cur=0;
        rep(j,n){
            int c=i&f[j],cnt=0;
            rep(k,10)if(c&(1<<k)) cnt++;
            cur+=p[j][cnt];
        }
        ans=max(ans,cur);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(void){
  	int Sum = 0;
  	int MAXNum = 0;
  	int N, L;
  	cin >> N;
  	for ( int i = 0; i < N; i++){
    	cin >> L;
      	Sum += L;
      	MAXNum = max(MAXNum,L);
    }
  	if ( Sum - MAXNum > MAXNum ) cout << "Yes" << endl;
  	else cout << "No" << endl;
	return 0;
}


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

int cont=0;
vector<int> visits;
vector<long long> conts;

int jump(int n){
  if(n<0) return 0;
  if(visits[n] == -1) return 0;
  if(visits[n] == 1) return conts[n];
  conts[n]=(jump(n-1)+jump(n-2))%1000000007;
  //cout<<n<<" "<<conts[n]<<endl;
  visits[n]=1;
  return conts[n];
}


int main(){
  int n,m;
  cin>>n>>m;
  int h;
  visits.assign(n+1,0);
  conts.assign(n+1,0);
  visits[0]=1;
  visits[1]=1;
  conts[0]=1;
  conts[1]=1;
  for(int i=0;i<m;i++){
    cin>>h;
    visits[h]=-1;
    conts[n]=0;
  }
  cout<<jump(n)%1000000007<<endl;

  return 0;
}


Measured memory_bytes: 6144
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(t) t.begin(), t.end()
#define inrange(i, a, b) (((i)>= min((a), (b))) && ((i) <= max((a), (b))))
#define show(x) cout << #x << " is " << x << "\n";
typedef vector<ll> vi;
#define fi first
#define se second
const ll inf = 9e18;
const ll mod = 1e9 + 7;

void print(ll a[], ll n){for(ll i=0;i<n;i++){cout<<a[i]<<" ";}cout<<"\n";}
ll power(ll x, ll y, ll M = inf){
    ll ans = 1;
    x %= M;
    while(y){
        if(y&1)
            ans = (x * ans) % M;

        x = (x * x) % M;
        y >>= 1;
    }
    return ans;
}
ll modInverse(ll n) {return power(n, mod-2, mod);}
inline ll mul(ll a, ll b){ return (a * b) % mod; }
inline ll sub(ll a, ll b){ ll c = a - b; if(c < 0) c += mod; return c; }
inline ll add(ll a, ll b){ ll c = a + b; if(c > mod) c -= mod; return c; }
inline ll divi(ll a, ll b){ return mul(a, modInverse(b)); }

const ll N = 1e5 + 1;
vector<ll> adj[N];
//bool visited[N];
vector<ll> ans(N, -1);
ll c;

void dfs(ll s, ll par, ll dis){
    if(ans[s]==-1){
        
        c++;
    }
    else {
        //ans[s] = min(dis, ans[s]);
        return;
    }
    
	for(auto u : adj[s]){
	    if(u == par) continue;
	    dfs(u, s, dis+1);
	}
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

	ll n, m, u, v;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		cin>>u>>v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	bool *visited = new bool[n+1]; 
    for(int i = 0; i < n+1; i++) 
        visited[i] = false; 
  
    list<pair<int, int> > queue; 
    pair<int, int> s = {1, 0};
    visited[1] = true; 
    queue.push_back(s); 

    while(!queue.empty()) 
    { 
        s = queue.front(); 
        ans[s.fi] = s.se;
        c++;
        if(c==n) break;
        
        queue.pop_front(); 
        for (auto i = adj[s.fi].begin(); i != adj[s.fi].end(); ++i) 
        { 
            if (!visited[*i]) 
            { 
                visited[*i] = true; 
                queue.push_back({*i, s.fi}); 
            } 
        } 
    } 
	if(c != n) {
		cout<<"No\n";
		return 0;
	}
	cout<<"Yes\n";
	for(int i=2;i<=n;i++){
		cout<<ans[i]<<"\n";
	}

	return 0;
}


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

#define ASC(vec) vec.begin(), vec.end()		// 昇順ソート 例：sort(ASC(vec));
#define DESC(vec) vec.rbegin(), vec.rend()	// 降順ソート 例:sort(DESC(vec));
#define rep(i, n) for(int i = 0; i < (n); i++)
#define Rep(i, n) for(int i = 1; i < n; i++)

const int mod = 1000000007;
const int inf = (1 << 21);
const long long INF = 1LL << 60;

using ii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
using vd = vector<double>;
using vb = vector<bool>;
using vl = vector<ll>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvb = vector<vector<bool>>;
using vii = vector<pair<int, int>>;

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; }

ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
ll LCM(ll a, ll b) { return (a * b) / GCD(a, b); }
int round_int(int a, int b) { return (a + (b - 1)) / b; }

constexpr array<int, 9> dx = { 0, 1, 0, -1, -1, 1, 1, -1, 0 };
constexpr array<int, 9> dy = { 1, 0, -1, 0, 1, 1, -1, -1, 0 };

// ──────────────────────────────────────────────────────────────────

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	if (a < b && b < c) cout << "Yes" << endl;
	else cout << "No" << endl;
}


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

int main(){
	int n; cin>>n;
	int ac=0,tle=0,wa=0,re=0;
	rep(i,n){
		char c[4]={}; cin>>c;
		if(c[0]=='A') ac++;
		else if(c[0]=='W') wa++;
		else if(c[0]=='T') tle++;
		else re++;
	}
	cout<<"AC x "<<ac<<endl;
	cout<<"WA x "<<wa<<endl;
	cout<<"TLE x "<<tle<<endl;
	cout<<"RE x "<<re<<endl;

}

Measured memory_bytes: 3616
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=605;
const int mod=1e9+7;
int n,m,mat[N],s[N],g[N],f[N][N],ans;
int main(){
	scanf("%d%d",&n,&m);n<<=1;
	for(int i=1;i<=n;++i)s[i]=1;
	for(int i=1,x,y;i<=m;++i){
		scanf("%d%d",&x,&y);
		mat[x]=y;mat[y]=x;s[x]=s[y]=0;
	}
	for(int i=1;i<=n;++i)s[i]+=s[i-1];
	g[0]=1;
	for(int i=2;i<=n;i+=2)g[i]=1ll*(i-1)*g[i-2]%mod;
	for(int i=n;i;--i)
		for(int j=i;j<=n;++j)
			if(j-i&1){
				int fg=1;
				for(int k=i;k<=j;++k)
					if(mat[k]&&(mat[k]<i||mat[k]>j))
						fg=0;
				if(!fg)continue;
				for(int k=i+1;k<j;++k)
					if(k-i&1)
						f[i][j]=(f[i][j]+1ll*f[i][k]*g[s[j]-s[k]])%mod;
				f[i][j]=(g[s[j]-s[i-1]]+mod-f[i][j])%mod;
				ans=(ans+1ll*f[i][j]*g[n-m-m-s[j]+s[i-1]])%mod;
			}
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 1536
import std.stdio, std.conv, std.functional, std.string;
import std.algorithm, std.array, std.container, std.range, std.typecons;
import std.numeric, std.math, std.random;
import core.bitop;

string FMT_F = "%.10f";

static File _f;
void file_io(string fn) { _f = File(fn, "r"); }
static string[] s_rd;
T _RD(T = long)() { while(!s_rd.length) s_rd = readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
T _RD(T = long)(File f) { while(!s_rd.length) s_rd = f.readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
T[] _RDA(T = long)(T fix = 0) { auto r = readln.chomp.split.to!(T[]); r[] += fix; return r; }
T[] _RDA(T = long)(File f, T fix = 0) { auto r = f.readln.chomp.split.to!(T[]); r[] += fix; return r; }
T RD(T = long)() { if (_f.isOpen) return _RD!T(_f); else return _RD!T; }
T[] RDA(T = long)(T fix = 0) { if (_f.isOpen)  return _RDA!T(_f, fix); else return _RDA!T(fix); }

size_t[] MAKE_IDX(alias less = "a < b", Range)(Range range) { auto idx = new size_t[](range.length); makeIndex!(less)(range, idx); return idx;}
size_t MIN_POS(alias less = "a < b", Range)(Range range) { auto r = minPos!(less)(range); return range.length - r.length; }

bool inside(T)(T x, T b, T e) { return x >= b && x < e; }
long lcm(long x, long y) { return x * (y / gcd(x, y)); }

//long mod = 10^^9 + 7;
long mod = 998244353;
//long mod = 1_000_003;
void moda(ref long x, long y) { x = (x + y) % mod; }
void mods(ref long x, long y) { x = ((x + mod) - (y % mod)) % mod; }
void modm(ref long x, long y) { x = (x * y) % mod; }

void main()
{
	auto N = RD;
	auto LR = new long[][](N, 2);
	foreach (i; 0..N)
	{
		LR[i] = [RD, RD];
	}
	LR.sort!"a[0] < b[0]"();

	auto a = new long[][](N+1, 2);
	a[0] = [0, 10L^^9];
	foreach (i; 0..N)
	{
		auto l = max(a[i][0], LR[i][0]);
		auto r = min(a[i][1], LR[i][1]);
		a[i+1] = [l, r];
	}

	auto b = new long[][](N+1, 2);
	b[$-1] = [0, 10L^^9];
	foreach_reverse (i; 0..N)
	{
		auto l = max(b[i+1][0], LR[i][0]);
		auto r = min(b[i+1][1], LR[i][1]);
		b[i] = [l, r];
	}
	debug writeln("a:", a);
	debug writeln("b:", b);

	long ans;
	foreach (i; 0..N-1)
	{
		auto range1 = max(a[i+1][1] - a[i+1][0] + 1, 0);
		auto range2 = max(b[i+1][1] - b[i+1][0] + 1, 0);
		ans = max(ans, range1 + range2);
		debug writeln("i:", i, " ans:", ans);
	}

	{
		auto base = LR[0][1] - LR[0][0] + 1;
		auto range = max(b[1][1] - b[1][0] + 1, 0);
		ans = max(ans, base + range);
	}
	{
		auto base = LR[$-1][1] - LR[$-1][0] + 1;
		auto range = max(a[$-2][1] - a[$-2][0] + 1, 0);
		ans = max(ans, base + range);
	}
	foreach (i; 1..N-1)
	{
		auto base = LR[i][1] - LR[i][0] + 1;
		auto l = max(a[i+1][0], b[i+1][0]);
		auto r = min(a[i+1][1], b[i+1][1]);
		auto range = max(r - l + 1, 0);
		ans = max(ans, base + range);
	}

	writeln(ans);
	stdout.flush();
	debug readln();
}

Measured memory_bytes: 26364
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(a) int((a).size())
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef pair<int, int> pii;
const int mod = 1e9 + 7;
template<class T, class U> inline void add_self(T &a, U b){a += b;if (a >= mod) a -= mod;if (a < 0) a += mod;}
template<class T, class U> inline void min_self(T &x, U y) { if (y < x) x = y; }
template<class T, class U> inline void max_self(T &x, U y) { if (y > x) x = y; }

#define _deb(x) cout<<x;
void _print() {cerr << "]\n";} template <typename T, typename... V>void _print(T t, V... v) {_deb(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define deb(x...) cerr << "[" << #x << "] = ["; _print(x)
template <class T, class U> void print_m(const map<T,U> &m, int w=3){if(m.empty()){cout<<"Empty"<<endl; return;}for(auto x: m)cout<<"("<<x.first<<": "<<x.second<<"),"<<endl;cout<<endl;}
template<class T, class U>void debp(const pair<T, U> &pr, bool end_line=1){cout<<"{"<<pr.first<<" "<<pr.second<<"}"; cout<<(end_line ? "\n" : ", ");}
template <class T> void print_vp(const T &vp, int sep_line=0){if(vp.empty()){cout<<"Empty"<<endl; return;}if(!sep_line) cout<<"{ ";for(auto x: vp) debp(x,sep_line);if(!sep_line) cout<<"}\n";cout<<endl;}
template <typename T>void print(const T &v, bool show_index = false){int w = 2;if(show_index){for(int i=0; i<sz(v); i++)cout<<setw(w)<<i<<" ";cout<<endl;}for(auto &el: v) cout<<setw(w)<<el<<" ";cout<<endl;}
template <typename T>void print_vv(const T &vv){if(sz(vv)==0) {cout<<"Empty"<<endl; return;} int w = 3;cout<<setw(w)<<" ";for(int j=0; j<sz(*vv.begin()); j++)cout<<setw(w)<<j<<" ";cout<<endl;int i = 0;for(auto &v: vv){cout<<i++<<" {";for(auto &el: v) cout<<setw(w)<<el<<" ";cout<<"},\n";}cout<<endl;}

const int nax = 1e6+10;
int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    while(cin>>n){
        vi a(n); forn(i,n) cin>>a[i];
        vi cnt(nax);
        for(auto x: a) cnt[x]++;

        if(cnt[1]){
            if(cnt[1]==1){
                cout<<1<<"\n";
            }else{
                cout<<0<<endl;
            }
            continue;
        }

        vb good(nax,1);
        for(int i=2; i<=1e6; ++i){
            if(cnt[i]){
                for(int j=2*i; j<=1e6; j+=i){
                    good[j] = false;
                }
            }
        }

        int ans = n;
        for(int i=1; i<=1e6; ++i){
            if(cnt[i]){
                // deb(i,cnt[i]);
                if(cnt[i]==1){
                    if(!good[i]) --ans;
                }else{
                    ans-=cnt[i];
                }
            }
        }

        cout<<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 8144
#include <iostream>
#include <algorithm>
#include <utility>
#define llint long long

using namespace std;
typedef pair<llint, llint> P;

llint n, m;
P p[10005];

int main(void)
{
	while(1){
		cin >> n >> m;
		if(n == 0 && m == 0) break;
		llint x, y, ans = 0;
		for(int i = 1; i <= n; i++){
			cin >> x >> y;
			p[i] = P(y, x);
			ans += x * y;
		}
		sort(p+1, p+n+1);
		reverse(p+1, p+n+1);
		
		llint rem = m;
		for(int i = 1; i <= n; i++){
			x = min(rem, p[i].second);
			ans -= p[i].first * x;
			rem -= x;
		}
		cout << ans << endl;
	}
	
	return 0;
}


Measured memory_bytes: 3256
#include <bits/stdc++.h>
#define int long long
#define iris 1000000007
using namespace std;

int x[1010],y[1010],arr[32];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n,m,a,b,i,j;
	bool flag;
	cin>>n;
	for(i=0;i<n;i++)
	{
		cin>>x[i]>>y[i];
		if(!i)
		{
			flag=(abs(x[i]+y[i])&1);
		}
		else if((abs(x[i]+y[i])&1)!=flag)
		{
			cout<<"-1\n";
			return 0;
		}
	}
	
	if(flag)
	{
		m=31;
		cout<<m<<'\n';
		for(i=0;i<m;i++)
		{
			arr[i]=(1<<(31-i-1));
			cout<<arr[i]<<" \n"[i==m-1];
		}
	}
	else
	{
		m=32;
		cout<<m<<"\n";
		for(i=0;i<m;i++)
		{
			arr[i]=(1<<max(31-i-1, 0LL));
			cout<<arr[i]<<" \n"[i==m-1];
		}
	}
	
	for(i=0;i<n;i++)
	{
		a=b=0;
		for(j=0;j<m;j++)
		{
			if(abs(x[i]-a)>abs(y[i]-b))
			{
				if(a<x[i])
				{
					a+=arr[j];
					cout<<"R";
				}
				else
				{
					a-=arr[j];
					cout<<"L";
				}
			}
			else
			{
				if(b<y[i])
				{
					b+=arr[j];
					cout<<"U";
				}
				else
				{
					b-=arr[j];
					cout<<"D";
				}
			}
		}
		cout<<"\n";
//		cout<<a<<' '<<b<<'\n';
	}
	
	return 0;
}

Measured memory_bytes: 256
import math

def read():
    N = int(input().strip())
    return N,


def solve(N):
    tax = 1.08
    x_lower = math.floor(N / tax)
    x_upper = math.ceil(N / tax)
    for x in range(x_lower, x_upper+1):
        if math.floor(x * tax) == N:
            return x
    return ':('
    
if __name__ == '__main__':
    inputs = read()
    output = solve(*inputs)
    print("%s" % output)


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

using namespace std;

using ll = long long;

void calc(const string& a, const string& b, vector<int>& res) {
    int na = a.size(), nb = b.size();

    res.resize(na + 1, true);
    for (int i = 0; i < na; ++i) {
        for (int j = 0; j < nb; ++j) {
            if (i + j >= na) break;
            if (a[i + j] != b[j] && a[i + j] != '?' && b[j] != '?') {
                res[i] = false;
                break;
            }
        }
    }
}

int solve(const string& a, const string& b, const string& c) {
    int na = a.size(), nb = b.size(), nc = c.size();

    vector<int> dp_ab, dp_bc, dp_ac;
    calc(a, b, dp_ab);
    calc(b, c, dp_bc);
    calc(a, c, dp_ac);

    int ans = na + nb + nc;
    for (int i = 0; i <= 4000; ++i) {
        if (!dp_ab[min(i, na)]) continue;
        for (int j = 0; j <= 4000; ++j) {
            if (!dp_bc[min(j, nb)] || !dp_ac[min(i + j, na)]) continue;
            ans = min(ans, max({na, i + nb, i + j + nc}));
        }
    }
    return ans;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    array<string, 3> vs;
    for (int i = 0; i < 3; ++i) {
        cin >> vs[i];
    }

    vector<int> ids = {0,1,2};
    int ans = 10000;
    do {
        ans = min(ans, solve(vs[ids[0]], vs[ids[1]], vs[ids[2]]));
    } while (next_permutation(ids.begin(), ids.end()));
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int G[9][9];
int n,m;
int ans;
main()
{
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int a,b;cin>>a>>b;
		G[a][b]=G[b][a]=1;
	}
	vector<int>v(n);
	for(int i=0;i<n;i++)v[i]=i+1;
	do{
		if(v[0]==1)
		{
			int flag=1;
			for(int i=0;i<n-1;i++)
			{
				if(G[v[i]][v[i+1]]==0)flag=0;
			}
			if(flag==1)ans++;
		}
	}while(next_permutation(v.begin(),v.end()));
	cout<<ans<<endl;
}


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

int N;
long long A, B, H[100005], h[100005];

bool attempt(int x) {
	for (int i = 0; i < N; i++) h[i] = max(0ll, H[i] - B * x);
	long long v = 0;
	for (int i = 0; i < N; i++) if (h[i] > 0) v += (h[i] - 1) / (A - B) + 1;
	if (x >= v) return 1;
	else return 0;
}

int main() {
	scanf("%d%lld%lld", &N, &A, &B);
	for (int i = 0; i < N; i++) scanf("%lld", &H[i]);
	int bot = 0, top = 1000000005, mid;
	while (bot + 1 < top) {
		mid = (bot + top)/2;
		if (attempt(mid)) top = mid;
		else bot = mid;
	}
	printf("%d\n", bot + 1);
}


Measured memory_bytes: 1792