akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

int beki(int, int);

int main()
{
	// 入力
	int x;
	cin >> x;

	int i, result, tmp, b;
	int a[10] = {};

	for (b = 2; b < 10; b++) {
		for (i = 1; ; i++) {
			tmp = beki(i, b);
			if (tmp > x) {
				a[b] = beki(i - 1, b);
				break;
			}
		}
	}
	result = 0;
	//max
	for (i = 2; i < 10; i++) {
		if (a[i] > result) {
			result = a[i];
		}
	}

	cout << result << endl;

	return 0;
}

int beki(int num, int b)
{
	int result = 1;
	for (int i = 0; i < b; i++) {
		result = result * num;
	}
	return result;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <cassert>
#include <string.h>
#include <iomanip>

using namespace std;

int main()
{
	int H,W, h, w;
	cin >> H >> W >> h >> w;
	
	cout << (H-h) * (W-w) <<endl;
	
	
	
	
	
	
	return 0;
}



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

#define int long long

auto main() -> signed {
    int n;
    cin >> n;
    string s;
    cin >> s;
    string ans = "";
    stack<int> st;
    for(int i=0; i<n; ++i) {
        char c = s[i];
        if(c=='(') {
            ans += "(";
            st.push(0);
        }
        else {
            if(!st.empty() && st.top() == 0) {
                ans += ")";
                st.pop();
            }
            else {
                ans += ")";
                st.push(1);
            }
        }
    }
    int u = st.size();
    for(int i=0; i<u; ++i) {
        if(st.top()==1) ans = "(" + ans;
        else ans += ")";
        st.pop();
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
// (setq-default c-basic-offset 2)

int main() {
  int x, n;
  cin >> x >> n;
  set<int> p;
  for (int i = 0; i < n; ++i) {
    int pi;
    cin >> pi;
    p.insert(pi);
  }

  int d = 0;

  while (true) {
    for (int s : {-1, 1}) {
      int ret = x + s * d;
      if (p.count(ret) == 0) {
        cout << ret << endl;
        return 0;
      }
    }
    ++d;
  }
  assert(false);
  return 0;
}


Measured memory_bytes: 3632
import sys
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
sys.setrecursionlimit(10**6)

n,m = na()
g = [[] for i in range(n)]
for i in range(m):
    a,b = na()
    a,b = a-1,b-1
    g[a].append(b)
    g[b].append(a)

for i in g[0]:
    if n-1 in g[i]:
        print('POSSIBLE')
        exit()

print('IMPOSSIBLE')

Measured memory_bytes: 50196
#include "bits/stdc++.h"
#define Rep(i,n) for(int i=0;i<(int)(n);i++)
#define For(i,n1,n2) for(int i=(int)(n1);i<(int)(n2);i++)
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i,n) for(ll i=((ll)(n)-1);i>=0;i--)
#define FOR(i,n1,n2) for(ll i=(ll)(n1);i<(ll)(n2);i++)
#define RFOR(i,n1,n2) for(ll i=((ll)(n1)-1);i>=(ll)(n2);i--)
#define all(a)  (a).begin(),(a).end()
#define IOS std::cin.tie(0),std::ios::sync_with_stdio(false)

namespace idaten {

	using namespace std;
	using ll = int_fast64_t;
	using ull = uint_fast64_t;
	using P = std::pair<int64_t, int64_t>;
	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<class Type>struct is_vector : std::false_type {};
	template<class ValueType, class Alloc>struct is_vector<std::vector<ValueType, Alloc>> : std::true_type {};
	template <typename T> inline std::ostream& operator << (std::ostream& out, const std::vector<T>& v) {
		if (v.empty())return out;
		constexpr bool is_vector_v = is_vector<T>::value;
		if (is_vector_v)for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? "\n" : "");
		else for (auto itr = v.begin(); itr != v.end();)out << (*itr), out << ((++itr != v.end()) ? " " : "");
		return out;
	}
	inline void put() {}
	template<class T> inline void put(const T& first) { std::cout << first << "\n"; }
	template<class T, class... N> inline void put(const T& first, const N& ... rest) { std::cout << first << " "; put(rest...); }
	inline void putn() {}
	template<class T, class... N> inline void putn(const T& first, const N& ... rest) { std::cout << first << "\n"; putn(rest...); }

	void solve() {
		IOS;
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		int t = (c + b - 1) / b;
		int t2 = (a + d - 1) / d;
		if (t <= t2) {
			put("Yes");
		} else {
			put("No");
		}
	}
} // namespace idaten

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


Measured memory_bytes: 3648
<?php
  
fscanf(STDIN,"%d %d",$N,$X);
$M = [];
for($i=1;$i<=$N;$i++){
  fscanf(STDIN,"%d",$M[$i]);
}
$min_cost_donut = min($M);
$count = $N;
$count+= intval(($X-array_sum($M)) / $min_cost_donut);

echo $count;

Measured memory_bytes: 3700
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
#include <cmath>
#define MAX_N 100010
const int MOD = 1e9 + 7;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<P> A(MAX_N, P(0, 0)), B(MAX_N, P(0, 0));
	int v[MAX_N];
	for(int i = 0; i < n; i++)
	{
		cin >> v[i];
		if(i % 2 == 0)
		{
			A[v[i]].first++;
			A[v[i]].second = v[i];
		}
		else
		{
			B[v[i]].first++;
			B[v[i]].second = v[i];
		}
	}
	sort(A.begin(), A.end());
	reverse(A.begin(), A.end());
	sort(B.begin(), B.end());
	reverse(B.begin(), B.end());
	int ans;
	if(A[0].second == B[0].second)
	{
		if(A[0].second > B[0].second)
			ans = n - (A[0].first + B[1].first);
		else if(A[0].second < B[0].second)
			ans = n - (A[1].first + B[0].first);
		else
			ans = n - A[0].first - max(A[1].first, B[1].first);
	}
	else
	{
		ans = n - (A[0].first + B[0].first);
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 2176
#include<bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(ll i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int gcd(int a, int b) {
	if (!b)return a;
	return gcd(b, a % b);
}
int lcm(int a, int b) {
	return a / gcd(a, b) * b;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n)cin >> a.at(i);
    ll g = a.at(0);
    REP(i, n-1)g = gcd(g, a.at(i));
    cout << g << endl;
}


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


#define INF 2147483647
#define LINF 9223372036854775807
#define MOD 1000000007
#define MOD2 998244353

template<class T,class U>bool chmax(T &a, const U &b){if(a<b){a=b;return 1;}return 0;}
template<class T,class U>bool chmin(T &a, const U &b){if(b<a){a=b;return 1;}return 0;}

#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
#define rep1(i,a,b) for(int a_=(a),b_=(b),i=a_;i<b_;++i)
#define repr(i,n) for(int _i=(n),i=_i;i>0;--i)

#define db(x) cerr<<#x<<" = "<<x<<" ";
#define db2(x,y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<") ";
#define db3(x,y,z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = ("<<x<<", "<<y<<", "<<z<<") ";
#define ln cout<<endl;

#define all(a)  (a).begin(),(a).end()
#define dig(n)  to_string(n).length()

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define se second
#define fi first

typedef long long ll;

typedef pair<int,int> P;
typedef pair<int,P> iP;
typedef pair<P,P> PP;

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 dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main(){

    bool flag=false;
    ll ans=0,sum=0;

    int n;
    cin>>n;
    vector<int> p(n),q(n);

    rep(i,n){
        cin>>p[i];
        q[ p[i]-1 ] = i;
    }

    int cnt=1,mx=1;
    rep1(i,1,n){
        if(q[i-1] < q[i])++cnt;
        else cnt = 1;
        chmax(mx,cnt);
    }

    cout<<n-mx<<endl;

    //cout <<fixed<<setprecision(16)<< << endl;
    //if(flag)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void){
    vector<unsigned int> d;
    unsigned int N;
    
    cin >> N;
    
    for(unsigned int i = 0;i < N;i++){
        unsigned int di;
        cin >> di;
        vector<unsigned>::iterator cIter = find( d.begin(),d.end() , di );

        if( cIter == d.end() ){
            d.push_back(di);
        }
    }
    
    cout << d.size();
}


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

////////////// Prewritten code follows. Look down for solution. ////////////////
#define x first
#define y second
#define len(x) ((int)(x).size())
using pii = pair<int, int>;
using ll = long long;
using llu = long long unsigned;
using ld = long double;

const ld EPS = 1e-9;
inline int cmp(ld x, ld y = 0, ld tol = EPS) {
	return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
}

const int MOD = 1e9 + 7;
inline int mod (ll x, int m = MOD) {
	return (int)(((x%m) + m)%m);
}

////////////////////////// Solution starts below. //////////////////////////////

const int N = 1001;

int n, m;
bool mat[N][N];
int dp[N][N];

int solve (int x, int y) {
	if (!mat[x][y]) return 0;
	if (x == n and y == m) return 1;
	int &r = dp[x][y];
	if (r != -1) return r;
	return r = mod (solve (x+1, y) + solve (x, y+1));
}

int main () {
	memset (dp, -1, sizeof dp);
	scanf ("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			char c; scanf (" %c", &c);
			mat[i][j] = c == '.';
		}
		
	printf ("%d\n", solve (1, 1));

	return 0;
}


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

#define  ll long long
#define  il inline
#define INF 0x3f3f3f3f
#define pii pair<int,int>

const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
const int maxm = 1e6 + 10;
const double PI = acos(-1.0);

int n , a, b, c, d;
string s;
int mp[maxn],dpb[maxn],dpa[maxn];


int main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    cin >> n >> a >> b >> c >> d >> s;
    for(int i = 0 ; i < n ;i++){
        if(s[i] == '.')mp[i] = 1;
        else mp[i] = 0;
    }
    a--,b--,c--,d--;
    dpa[a] = dpb[b] = 1;
    // b
    for(int i = b + 1 ; i <= d ; i++){
        if(mp[i])dpb[i] = (dpb[i - 1] | dpb[i - 2]);
        else dpb[i] = 0;
    }
    mp[d] = 0;
    for(int i = a + 1 ; i <= c ; i++){
        if(mp[i])dpa[i] = (dpa[i - 1] | dpa[i - 2]);
        else dpa[i] = 0;
    }
/*
    for(int i = 0 ; i < n ;i++)
        cout << dpa[i];
        cout << endl;
    for(int i = 0 ; i < n ;i++)
        cout << dpb[i];
*/
    mp[d] = 1;
    int ans = dpa[c]&dpb[d];
    int flag = 0;
    for(int i = 0 ; i <= d; i++){
         if(dpb[i]){
            if(i >= 1 && dpa[i - 1] && dpa[i + 1])flag = 1;
            if(i == d - 1 && dpa[i - 1]) flag = 1;
         }
    }
    //if(dpa[b-1] && dpa[b + 1])flag = 1;
    if(flag){
        memset(dpa,0,sizeof(dpa));
        memset(dpb,0,sizeof(dpb));
         dpa[a] = dpb[b] = 1;
         for(int i = a + 1 ; i <= c ; i++){
            if(mp[i])dpa[i] = (dpa[i - 1] | dpa[i - 2]);
            else dpa[i] = 0;
        }
        mp[c] = 0;
        for(int i = b + 1 ; i <= d ; i++){
           if(mp[i])dpb[i] = (dpb[i - 1] | dpb[i - 2]);
           else dpb[i] = 0;
       }
        ans |= (dpa[c]&dpb[d]);
        //cout << ans << endl;
        mp[c] = 1;
    }
    if(c > d){
        memset(dpa,0,sizeof(dpa));
        memset(dpb,0,sizeof(dpb));
        for(int i = b + 1 ; i < n ; i++){
        if(mp[i])dpb[i] = (dpb[i - 1] | dpb[i - 2]);
        else dpb[i] = 0;
       }
        for(int i = a + 1 ; i <= b ; i++){
        if(mp[i])dpa[i] = (dpa[i - 1] | dpa[i - 2]);
        else dpa[i] = 0;
       }
       if(dpa[b]){
       for(int i = b + 1; i <= d - 1; i++){
           if(dpb[i - 1] && dpb[i + 1]){
               ans |= dpb[d];
               break;
           }
       }
       }
    }

    if(ans)cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;

}



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


int main(){
    int A,B,M;
    cin >> A >> B >> M;
    int a[A],b[B],c[M];
    int x[M],y[M];
    for(int i = 0; i < A; i++){
        cin >> a[i];
    }
    for(int i = 0; i < B; i++){
        cin >> b[i];
    }
    for(int i = 0; i < M; i++){
        cin >> x[i] >> y[i] >> c[i];
    }
    int rei = 1000001;
    for(int i = 0; i < A; i++){
        rei = min(rei,a[i]);
    }
    int den = 1000001;
    for(int i = 0; i < B; i++){
        den = min(den,b[i]);
    }
    int sum = 2000001;
    for(int i = 0; i < M; i++){
        sum = min(a[x[i]-1] + b[y[i]-1] - c[i], sum);
    }
    cout << min(sum , den + rei) << endl;
}

Measured memory_bytes: 2176
N, W = map(int, input().split())

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
weight = []
value = []
for i in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)

for i in range(N):
    for sum_w in range(W+1):
        # i 番目の品物を選ぶ場合
        if sum_w >= weight[i]:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - weight[i]] + value[i])
        # i 番目の品物を選ばない場合
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

print(dp[N][W])


Measured memory_bytes: 171400
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
const int nmax=2005;
vector<int> v[nmax];
int dist[nmax][nmax];
int a[nmax],b[nmax];
int n,leafs,mn,start,k,i,j,D;
void dfs(int x)
{
    for(int i=0;i<v[x].size();i++)
        if(!dist[start][v[x][i]])
    {
        dist[start][v[x][i]]=dist[start][x]+1;
        dfs(v[x][i]);
    }
}
int main()
{
   // freopen("data.in","r",stdin);
    cin>>n>>k;
    for(i=1;i<=n-1;i++)
    {
        cin>>a[i]>>b[i];
        v[a[i]].push_back(b[i]);
        v[b[i]].push_back(a[i]);
    }
    for(start=1;start<=n;start++)
    {
        dist[start][start]=1;
        dfs(start);
    }
    mn=n;
    if(k%2==0)
    {
        for(i=1;i<=n;i++)
        {
            leafs=0;
            for(j=1;j<=n;j++)
            {
                D=dist[i][j]-1;
                if(D>k/2) leafs++;
            }
            mn=min(mn,leafs);
        }
    }
    else
    {
        for(i=1;i<=n-1;i++)
        {
            leafs=0;
            for(j=1;j<=n;j++)
            {
                D=min(dist[a[i]][j],dist[b[i]][j])-1;
                if(D>(k-1)/2) leafs++;
            }
            mn=min(mn,leafs);
        }
    }
    cout<<mn;
    return 0;
}


Measured memory_bytes: 16128
#include <iostream>
#include <cstring>
#include <map>
#include <stack>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef pair<int,int> pi;
typedef long long ll;
ll MOD = 1000000007;

int conn[55][55];
vector <int> g[55];
pi sta[10011];
int num[55],low[55],n,m,k,tim,top;
vector <pi> bcc[55]; int cnt;

void tarj(int v, int pa)
{
	low[v]=num[v]=++tim;
	for (int i=0; i<g[v].size(); i++)
	{
		int u=g[v][i];
		if (!num[u])
		{
			sta[++top]=pi(v,u);
			tarj(u,v);
			low[v]=min(low[v],low[u]);
			if (low[u]>=num[v])
			{
				cnt++;
				while(num[sta[top].first]>=num[u])
				{
					bcc[cnt].push_back(sta[top--]);			
				}
				bcc[cnt].push_back(sta[top--]);
			}
		}
		else if (num[u]<num[v]&&u!=pa)
		{
			sta[++top]=pi(v,u);
			low[v]=min(low[v],num[u]);
		}
	}	
}


ll gcd(ll a,ll b)
{
	return b==0?a:gcd(b,a%b);
}
ll mpow(ll x, ll n)
{
	ll res=1;
	while(n)
	{
		if (n&1) res=res*x%MOD;
		x=x*x%MOD;
		n/=2;
	}
	return res;
}
ll fac[2100],inv[2100];
ll conb(int n,int m)
{
	return fac[m]*inv[n]%MOD*inv[m-n]%MOD;
}
void init()
{
	fac[0]=1;
	for(int i=1; i<=2000; i++) fac[i]=fac[i-1]*i%MOD;
	inv[2000]=mpow(fac[2000],MOD-2);
	for(int i=1999; i>=0; i--)inv[i]=inv[i+1]*(i+1)%MOD;
}
int main()
{
	init();
	cin>>n>>m>>k;
	for (int i=1; i<=m; i++)
	{
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
		conn[v][u]=conn[u][v]=1;
	}
	
	for (int i=1; i<=n; i++)
	{
		top=0;
		if (!num[i]) tarj(i,0);
	}
	ll ans=1; //cout << cnt << endl;
	for (int i=1; i<=cnt; i++)
	{
		int v0=0; //cout << bcc[i].size() << endl;
		for (int j=1; j<=n; j++)
		{
			for (int k=0; k<bcc[i].size(); k++) 
			    if (bcc[i][k].first==j||bcc[i][k].second==j) 
				{
					v0++; //cout << j << ' ';
					break;
				}
		}
		if (v0==bcc[i].size())//polya
		{
			ll re=0;
			for (int r=0; r<v0; r++) re=(re+mpow(k,gcd(r,v0)))%MOD; //cout << re << endl;
			re=re*mpow(v0,MOD-2)%MOD; //cout << re << endl;
			ans=ans*re%MOD;
		}
		else if (v0<bcc[i].size())
		{
			//cout << bcc[i].size()+k-1 << ' ' << k-1 << endl;
			ll re=conb(k-1,bcc[i].size()+k-1); //cout << re << endl;
			ans=ans*re%MOD;
		}
		else ans=ans*k%MOD; //cout << endl;
	}
	cout << ans%MOD;
}

Measured memory_bytes: 256
//By Vlgd
#include<bits/stdc++.h>
using namespace std;
struct node{
	int x;
	node *l,*r,*p;
};
node* root=NULL;
void insert(int x){
	node *n=(node*)malloc(sizeof(node));
	n->x=x;
	n->r=n->l=NULL;
	node *tmp=root,*fa=NULL;
	while(tmp!=NULL){
		fa=tmp;
		if (x<tmp->x) tmp=tmp->l; 
		else tmp=tmp->r;
	}
	n->p=fa;
	if (fa==NULL){
		root=n;
	}
	else{
		if (x<fa->x) fa->l=n;
		else fa->r=n;
	}	
}
void ino(node *T){
	if (T!=NULL){
		ino(T->l);
		printf(" %d",T->x);
		ino(T->r);
	}
}
void pre(node *T){
	if (T!=NULL){
		printf(" %d",T->x);
		pre(T->l);
		pre(T->r);
	}
}
main(){
	int n,xx;
	string ins;
	scanf("%d",&n);
	for (int i=0;i<n;i++){
		cin>>ins;
		if (ins=="insert"){
			scanf("%d",&xx);
			insert(xx);
		}
		else if (ins=="print"){
			ino(root);printf("\n");
			pre(root);printf("\n");
		}
	}
}


Measured memory_bytes: 26704
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
using P = pair<ll,ll>;

class UnionFind {
public:
    vector < ll > par; // 各元の親を表す配列
    vector < ll > siz; // 素集合のサイズを表す配列(1 で初期化)

    // Constructor
    UnionFind(ll sz_): par(sz_), siz(sz_, 1) {
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1);
        for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
    }

    // Member Function
    // Find
    ll root(ll x) { // 根の検索
        while (par[x] != x) {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }

    // Union(Unite, Merge)
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) { // 連結判定
        return root(x) == root(y);
    }

    ll size(ll x) { // 素集合のサイズ
        return siz[root(x)];
    }
};

int main()
{
  ll N,M,K;
  cin >> N >> M >> K;
  UnionFind UF(N);
  vector<P> A(M);
  REP(i,M){
    cin >> A[i].first >> A[i].second;
    A[i].first--;
    A[i].second--;
    UF.merge(A[i].first,A[i].second);
  }

  vector<vector<ll>> vec(N,vector<ll> ()); 
  REP(i,M){
    vec.at(A[i].first).push_back(A[i].second);
    vec.at(A[i].second).push_back(A[i].first);
  }
  
  vector<P> B(K);
  vector<vector<ll>> vec2(N,vector<ll> ());
  REP(i,K){
    cin >> B[i].first >> B[i].second;
    B[i].first--;
    B[i].second--;
    if(UF.issame(B[i].first,B[i].second)){
      vec2.at(B[i].first).push_back(B[i].second);
      vec2.at(B[i].second).push_back(B[i].first);
    }
  }
  // REP(i,N){
  //   if(i!=N-1){
  //     cout << UF.size(i) << vec.at(i).size() << vec2.at(i).size() << " ";
  //   }else{
  //     cout << UF.size(i) << vec.at(i).size() << vec2.at(i).size() << endl;
  //   }
  // }
  REP(i,N){
    if(i!=N-1){
      cout << UF.size(i)-1-vec.at(i).size()-vec2.at(i).size() << " ";
    }else{
      cout << UF.size(i)-1-vec.at(i).size()-vec2.at(i).size() << endl;
    }
  }
}

Measured memory_bytes: 20008
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
//二項係数の計算
int nCr(int A, int B) {
    ll ans = 1;
    for (int i = 0; i < B; i++) {
        ans *= A - i;
    }
    for (int i = 0; i < B; i++) {
        ans /= i + 1;
    }
    return ans;
}
int main() {
   int N;
   cin>>N;
   vector<int>A(N);
   vector<int>K(10000000);
   int ans=0;
   rep(i,N){
       cin>>A[i];
        if(K[A[i]]==0){
            ans++;
            K[A[i]]++;
        }
   }
   cout<<ans<<endl;
}


Measured memory_bytes: 42324
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <map>
#include <set>
#include <vector>
#include <list>
#include <queue>
#include <sstream>
#include <cmath>
#include <functional>
#include <climits>
using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
#define reps(s,i,n) for(int i=s;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define skip(i,n,p) for(int i=0;i<n;i+=p)
#define all(a)  (a).begin(),(a).end()
#define int64 long long
#define debug cerr << __FILE__ << ":" << __LINE__ << endl;
#define INF 2147483647

struct Init {
    Init() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout.precision(20);
        cout << fixed;
        // setw(6) << setfill('0')
    }
} init;

template <typename _Ty>
ostream& operator << (ostream& ostr, const vector<_Ty>& v) {
    for(int i = 0; i < (int) v.size(); i++) {
        ostr << v[i] << (i + 1 != v.size() ? " " : "");
    }
    return ostr;
}

template <typename _K, typename _V>
ostream& operator << (ostream& ostr, const map<_K, _V>& v) {
    ostr << "{";
    for (auto iter = v.begin(); iter != v.end(); ++iter) {
        ostr << (*iter).first << ": " << (*iter).second << ", ";
    }
    ostr << "}";
    return ostr;
}

template <typename _K>
ostream& operator << (ostream& ostr, const set<_K>& v) {
    for (auto iter = v.begin(); iter != v.end(); ++iter) {
        ostr << *iter << (iter != v.end() ? " " : "");
    }
    return ostr;
}

template <typename _K, typename _V>
ostream& operator << (ostream& ostr, const pair<_K, _V>& v) {
    ostr << "(" << v.first << ", " << v.second << ")";
    return ostr;
}

vector<string> split(const string &s, char delim) {
    vector<string> result;
    stringstream ss(s);
    string item;
    while (getline(ss, item, delim)) {
        if (!item.empty()) {
            result.push_back(item);
        }
    }
    return result;
}

int64 gcd(int64 a, int64 b) {
    if (a < b) a, b = b, a;
    if (a % b == 0) return b;
    return gcd(b, a % b);
}

int main() {
    int N; cin >> N;
    vector<int> L(N); rep(i, N) cin >> L[i];

    sort(all(L));

    vector<int> v(1000019, 0);
    rep(i, N) {
        int t = L[i];
        if (v[t] != 0) {
            v[t]++;
            continue;
        }
        while (t < v.size()) {
            v[t]++;
            t += L[i];
        }
    }

    int ans = 0;
    rep(i, N) {
        if (v[L[i]] == 1) ans++;
    }

    cout << ans << endl;
}


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

int main() {
    string n;
    cin >> n;
    if (n.at(1) == n.at(2) && (n.at(0) == n.at(1) || n.at(3) == n.at(1))) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

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

namespace AtCoder.Abc
{
    //https://atcoder.jp/contests/abc081/tasks/abc081_b
    class Abc_081_B
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            // 整数の入力
            long n = long.Parse(Console.ReadLine());

            // 整数配列の入力
            var inputLongArray = Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();

            int result = 0;
            bool res = true;
            while (res)
            {
                for (int i = 0; i < inputLongArray.Length; i++)
                {
                    if (inputLongArray[i] % 2 != 0)
                    {
                        Console.WriteLine(result);
                        Console.Out.Flush();
                        return;
                    }
                }
                for (int i = 0; i < inputLongArray.Length; i++)
                {
                    inputLongArray[i] = inputLongArray[i] / 2;
                }
                result++;
            }
        }
    }
}


Measured memory_bytes: 13396
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(long long i = 0;i < n;i++)
#define repr(i, n) for(int i = n;i >= 0;i--)
#define For(i, s, e) for(int i = s;i <= e;i++)
#define Sort(v, n) sort(v, v+n);
#define VSort(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999
#define cY cout<<"Yes";
#define cN cout<<"No";
#define cA(a) cout<<a;
const ll MOD = 1000000007;

int main() {
    string s;
    cin >> s;
    int a[3];
    rep(i,3) {
        a[i] =0;
    }
    rep(i,s.size()) {
        if(s[i] == 'a')a[0]++;
        if(s[i] == 'b')a[1]++;
        if(s[i] == 'c')a[2]++;
    }
    int limit;
    if(s.size()%3==0) {
        limit = s.size()/3;
    } else {
        limit = (s.size()/3)+1;
    }
    if(a[0] <=limit&& a[1] <=limit&&a[2] <=limit) {
        cout << "YES";
    } else {
        cout << "NO";
    }
}


Measured memory_bytes: 512
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mii map <int, int>
#define mll map <ll, ll>
#define pii pair <int, int>
#define pll pair <ll, ll>
#define vi vector <int>
#define vd vector <double>
#define vll vector <ll>
#define fi first
#define se second
#define si set <int>
#define sll set <ll>
#define spii set <pii>
#define vs vector <string>
#define vpii vector <pair <int,int> >
#define vpll vector <pair <long long,long long> >
#define vvi vector <vector <int> >
#define vvpii vector <vector <pii > >
#define forn(i, n) for (int i = 0; i < (n); i++)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define for1(i, n) for (int i = 1; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(),(x).rend()


using namespace std;
const ll INFLL = 1e18;
const int MAXN = 1e6+100;
const ll INF = 1e9;
const ll mod1=1e9+7;
const ll mod2=2e9+11;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef LOCAL
    freopen("a.in","r",stdin);
    #endif
    ll x;
    cin>>x;
    cout<<2*(x/500)*500+((x%500)/5)*5;




}

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

int n;
ll w;
ll W[111];
ll V[111];
ll dp[111][100010];
const long long INF = 1LL<<60;


ll min(ll a, ll b) {
    return a > b ? b : a;
}

int main(void){
    // Your code here!
    /* dp[i+1][j] i番目までのアイテムを使用して価値がjとなるときの最小の重み */
    cin >> n >> w;
    ll val = 0;
    for(int i = 0; i < n; i++) {
        cin >> W[i] >> V[i];
        val += V[i];    
    }
    
    for(int i = 0; i <=110; i++) for(int j = 0; j < 100010; j++) dp[i][j] = INF;
     
     
    dp[0][0] = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 100010; j++){
            if(j-V[i] >= 0) dp[i+1][j] = min(dp[i+1][j], dp[i][j - V[i]] + W[i]);
            dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
        }
    }
    
    ll ans = 0;
    for(int j = 0; j < 100010; j++) {
        if(dp[n][j] <= w){
            ans = j;
        }
    }
    cout << ans << endl;
    return 0;
}


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

int main() {
  long long a, b, c;
  std::cin >> a >> b >> c;
  long long l = 4 * a * b, r = c - a - b;
  if (r < 0) {
    std::cout << "No\n";
  }
  else {
    std::cout << (l < r * r ? "Yes" : "No") << '\n';
  }
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define dl double
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define mod 1e9+7
#define P(a,b) pair<a,b>
#define CIN(V,s,n) for(int i=s;i<n;i++){cin >> V[i];}
#define COUT(V,s,n) for(int i=s;i<n;i++){cout <<  V[i] << " ";}

using namespace std;
bool sortBylen(string &a,string &b)
{
    if(a.size()>b.size())
        return true;
    else if(a.size()==b.size())
    {
        if(a>b)
        {
            return true;
        }
        else
            false;
    }
    else
        return false;
}
int main()
{
ll t=1;
//cin >> t;
while(t--)
{
    ll n,W,i,j,k=2,l,m;
    cin >> n >> W;
    vector<ll> w(n),v(n);
    ll maxV=0;
    for(i=0;i<n;i++)
    {
        cin >> w[i] >> v[i];
        maxV += v[i];
    }
    vector<vector<ll> > DP(n+1,vector<ll>(maxV+1,1e12));
    for(i=0;i<=n;i++)
    {
        DP[i][0]=0;
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=maxV;j++)
        {
            DP[i][j] = DP[i-1][j];
            if(v[i-1]<=j)
            {
                DP[i][j] = min(DP[i-1][j],DP[i-1][j-v[i-1]] + w[i-1]);
            }
        }
    }
    ll ans = 0;
    for(i=0;i<=maxV;i++)
    {
        if(DP[n][i]<=W and ans < i)
            ans = i;
    }
    cout << ans << endl;
}

	return 0;
}


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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader input =new BufferedReader(new InputStreamReader(System.in));
        String[] s = input.readLine().split(" ");
        StringBuilder builder = new StringBuilder("");
        builder.append(s[0].charAt(0));
        builder.append(s[1].charAt(0));
        builder.append(s[2].charAt(0));
        System.out.println(builder.toString());
    }
}

Measured memory_bytes: 21204
#include <iostream>
using namespace std;
int main()
{
  long long int n, x;
  cin >> n;
  x = ( -1.0 + sqrt( 1.0 + 8.0 * n ) ) / 2.0;
  if( n - x * ( x+1 ) / 2 == 0 )
    cout << x;
  else
    cout << x+1;
}
  

Measured memory_bytes: 3132
#include <bits/stdc++.h>
const int MOD = 1e9+7;
#define REP(i,n) for (int i = 0; i < (n); ++i)
#define ll long long
#define ar array
using namespace std;
using P = pair<int,int>;

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

	int X,Y;
	cin >> X >> Y;

	cout << X+(Y/2) << endl;
	return 0;
}


Measured memory_bytes: 3580
/**
 *  author: mahfuzz
 *  created: 17.12.2019
**/
 
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cout << #x << ':' << x << "\n";
//~ const double pi = 2*acos(0.0);
//~ const long long mod = 1e9+7;
//~ const int max_n = 1e6+5;
typedef long long ll;

int main(int argc, char* argv[]){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    
    int a, b, c;
    cin >> a >> b >> c;
    
    if(a+b+c >= 22)
        cout << "bust\n";
    else
        cout << "win\n";
    
        
    return 0;
}


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

#define clean(x,y) memset(x,y,sizeof(x));
#define pb push_back
#define F first
#define S second
#define LB lower_bound
#define UB upper_bound
#define ALL(v) v.begin(),v.end()
#define PI acos(-1.0)
#define EPS 1e-9
#define INF (1 << 30)
#define MOD 1000000007
#define MAX 200005
#define endl "\n"
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
#define dbg(x) cout<<(#x)<<"="<<(x)<<":\n"
#define CS(i) cout<<"Case "<<i<<": "
#define tin ll T; cin>>T; while(T--)

typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

///O(r)
ll C(ll n, ll r)
{
    if(r>n) return 0;

    double fact=1.0;
    for(ll i=1; i<=r; ++i)
        fact=fact*(n-r+i)/i;

    return (ll)(fact+EPS);
}

ll a[MAX],cnt[MAX];

int main()
{
    FAST

    ll n,i,j,x,y,ans=0;

    cin>>n;
    for(i=0; i<n; i++)
    {
        cin>>x;
        cnt[x]++;
        a[i]=x;
    }

    for(i=1; i<=n; i++)
        ans+=C(cnt[i],2ll);
    for(i=0; i<n; i++)
    {
        x=C(cnt[a[i]],2ll);
        y=C(cnt[a[i]]-1,2ll);
        cout<<ans-x+y<<endl;
    }



    return 0;
}




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

using namespace std;
 
int main() {
int N;
cin >> N;
vector<int> a(N);
for (int i = 0; i < N; i++)
{
    cin >> a.at(i);
}

int count = 0;

while (true)
{
    bool exist_odd = false;

    for (int i = 0; i < N; i++)
    {
        if (a.at(i) % 2 != 0)
        {
            exist_odd = true;
        }
    }   
    
    if (exist_odd == true)
    {
        break;
    }
    
    for (int i = 0; i < N; i++)
    {
        a.at(i) = a.at(i)/2;
    }
        count = count + 1;
}   
cout << count << endl;

}

Measured memory_bytes: 256
n, k = map(int, input().split())
p_list = list(map(lambda x: int(x) - 1, input().split()))
c_list = list(map(int, input().split()))

max_score = -(1 << 64)
cycles = []
cycled = [False] * n
for i in range(n):
    if cycled[i]:
        continue

    cycle = [i]
    cycled[i] = True
    while p_list[cycle[-1]] != cycle[0]:
        cycle.append(p_list[cycle[-1]])
        cycled[cycle[-1]] = True

    cycles.append(cycle)

for cycle in cycles:
    cycle_len = len(cycle)

    accum = [0]
    for i in range(cycle_len * 2):
        accum.append(accum[-1] + c_list[cycle[i % cycle_len]])

    cycle_score = accum[cycle_len]

    max_series_sums = [max([accum[i + length] - accum[i]
                            for i in range(cycle_len)])
                       for length in range(cycle_len + 1)]

    if cycle_len >= k:
        score = max(max_series_sums[1:k + 1])
    elif cycle_score <= 0:
        score = max(max_series_sums[1:])
    else:
        max_cycle_num, cycle_rem = divmod(k, cycle_len)
        score = max(cycle_score * (max_cycle_num - 1) + max(max_series_sums),
                    cycle_score * max_cycle_num + max(max_series_sums[:cycle_rem + 1]))

    max_score = max(max_score, score)

print(max_score)


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

using namespace std;

#ifdef NeverBeRed
#include "debug.h"
#else
#define debug(...) 9715
#endif
typedef long long ll;
typedef long double ld;
typedef complex<ld> point;
#define F first
#define S second



int main()
{
	#ifdef TurnRed
		//freopen("a.in", "r", stdin);
		//freopen("a.out", "w", stdout);
	#endif

	ios_base::sync_with_stdio(0), cin.tie(0);

	int x;
	cin >> x;
	cout << 360 / __gcd(360, x) << "\n";

	return 0;
}


Measured memory_bytes: 3636
#include <stdio.h>

int main()
{
  int i,j,minj,x,y,cnt,N,A[100];

  scanf("%d",&N);
  for(i = 0;i < N;i++) scanf("%d",&A[i]);

  for(i = 0;i < N;i++){
    minj = i;
    for(j = i;j < N;j++){
      if(A[j] < A[minj]) minj = j;
    }
    if(i != minj){
      x = A[i];
      y = A[minj];
      A[i] = y;
      A[minj] = x;
      cnt++;
    }
  }

    for(i = 0;i < N;i++){
      printf("%d",A[i]);
      if(i < N-1) printf(" ");
      else printf("\n");
    }
    printf("%d\n",cnt);

    return 0;
}



Measured memory_bytes: 2104
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<cstdio>
#include<bitset>
#include<unordered_map>
using namespace std;
//---------------------------------------------------
//ライブラリゾーン！！！！
typedef long long ll;
typedef long double ld;
#define str string
#define rep(i,j) for(ll i=0;i<(long long)(j);i++)
#define all(a) (a).begin(),(a).end()
const ll Mod = 1000000007;
const ll gosenchou = 5000000000000000;
short gh[2][4] = { { 0,0,-1,1 },{ -1,1,0,0 } };
struct P {
	ll pos, cost;
};
bool operator<(P a, P b) { return a.cost < b.cost; }
bool operator>(P a, P b) { return a.cost > b.cost; }
struct B {//隣接リスト表現
	ll to, cost;
};
struct E {//辺の情報を入れる変数
	ll from, to, cost;
};
bool operator<(E a, E b) {
	return a.cost < b.cost;
}
struct H {
	ll x, y;
};
bool operator<(H a, H b) {
	if (a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}
bool operator>(H a, H b) {
	if (a.x != b.x) return a.x > b.x;
	return a.y > b.y;
}
bool operator==(H a, H b) {
	return a.x == b.x&&a.y == b.y;
}
bool operator!=(H a, H b) {
	return a.x != b.x || a.y != b.y;
}
ll gcm(ll i, ll j) {//最大公約数
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcm(j%i, i);
}
ld rad(H a, H b) {
	return sqrt(pow(a.x - b.x, 2.0) + pow(a.y - b.y, 2.0));
}//rad＝座標上の2点間の距離
ll ari(ll a, ll b, ll c) {
	return (a + b)*c / 2;
}//等差数列の和
ll fact(ll x, ll k, ll p) {//最大値、個数、あまり
	ll sum = 1;
	for (int i = 0; i < k; i++) {
		sum *= (x--);
		sum %= p;
	}
	return sum;
}//階乗(正）
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res*x%p;
		x = x*x%p;
		n >>= 1;
	}
	return res;
}//x^n%p
short ctos(char a) {
	return (int)(a - '0');
}
#define int long long
const long long Inf = 4523372036854775807;
const int inf = 15000000000;
//----------------------------------------------------
//++++++++++++++++++++++++++++++++++++++++++++++++++++
signed main() {
	int a,b,c;
	cin>>a>>b>>c;
	for(int i=1;i<=a+10;i++){
		int sum=b*i+c;
		if(sum%a==0){
			cout<<"YES\n";
			return 0;
		}
	}
	cout<<"NO\n";
}


Measured memory_bytes: 384
def factorial_memo(n, p):
  F = [1] * (n + 1)
  for i in range(n):
    F[i + 1] = F[i] * (i + 1) % p
  return F

def inverse(F, p):
  Finv = [x for x in F]
  Finv[-1] = pow(Finv[-1], p - 2, p)
  for i in range(len(F) - 2, 0, -1):
    Finv[i] = Finv[i + 1] * (i + 1) % p
  return Finv

def comb(a, b):
  if a < b:
    return 0
  return F[a] * Finv[a - b] * Finv[b] % p

n = int(input())
A = [int(x) for x in input().split()]
p = 10 ** 9 + 7
D = [-1] * n
double = [-1, -1]
for i, a in enumerate(A):
  if D[a - 1] == -1:
    D[a - 1] = i
  else:
    double = [D[a - 1], i]
    break
F = factorial_memo(n + 1, p)
Finv = inverse(F, p)
n_a = double[0]
n_b = n - double[1]
print(n)
C = [0] * n
for i in range(2, n + 2):
  cnt = (comb(n + 1, i) - comb(n_a + n_b, i - 1)) % p
  print(cnt)

Measured memory_bytes: 21252
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        long n = Integer.parseInt(sc.next());
        long m = Integer.parseInt(sc.next());

        long ans = 0;
        if(n == 1 && m == 1){
            ans = 1;
        }else if(n == 1 && m > 1){
            ans = m-2;
        }else if(m == 1 && n > 1){
            ans = n-2;
        }else if(n > 1){
            ans = (n-2)*(m-2);
        }
        
        System.out.println(ans);
    }
    
}

Measured memory_bytes: 21844
#include<algorithm> // sort,reverse,min,lower_bound
#include<vector>

#include<iostream>
using namespace std;
#define df 0
#define rep(i,n) for(int i=0;i<(n);i++)
#define repa(i,a,n) for(int i=(a);i<(n);i++)
typedef long int li;

void print(vector<li>& v){
  for(li x: v) printf("%ld ",x);
  printf("\n");
}

int main(){
  if(df) printf("*debug mode*\n");
  int n,w; cin >>n >>w;
  vector<vector<li>> v(4);
  li w0; cin >>w0;
  li v0; cin >>v0; v.at(0).push_back(v0);
  rep(i,n-1){
    li w,a; cin >>w >>a;
    v.at((int)(w-w0)).push_back(a);
  }
  rep(i,4){
    sort(v.at(i).begin(),v.at(i).end());
    reverse(v.at(i).begin(),v.at(i).end());
  }
  vector<vector<li>> s(4);
  rep(i,4){
    s.at(i).push_back(0);
    for(li x: v.at(i)){
      s.at(i).push_back(s.at(i).back()+x);
    }
  }
  if(df){
    for(vector<li>& vec:v)print(vec);
    for(vector<li>& vec:s)print(vec);
  }

  li now=0,ans=0;
  rep(i,s.at(0).size()){
    if(df)printf("nowi:%ld.",now);
    if(now>w){
      now-=(w0)*i;
      break;
    }
    rep(j,s.at(1).size()){
      if(df)printf("nowj:%ld.",now);
      if(now>w){
	now+=(w0+1)*(s.at(1).size()-j);
	break;
      }
      rep(k,s.at(2).size()){
	if(df)printf("nowk:%ld.",now);
	if(now>w){
	  now+=(w0+2)*(s.at(2).size()-k);
	  break;
	}
	rep(l,s.at(3).size()){
	  if(df)printf("nowl:%ld.",now);
	  if(now>w){
	    now+=(w0+3)*(s.at(3).size()-l);
	    break;
	  }
	  li tempv=s.at(0).at(i)+s.at(1).at(j)+s.at(2).at(k)+s.at(3).at(l);
	  if(df)printf(":%ld\n",tempv);
	  if(ans<tempv) ans=tempv;
	  now+=w0+3;
	}
	now-=(w0+3)*(s.at(3).size());

	now+=w0+2;
      }
      now-=(w0+2)*(s.at(2).size());

      now+=w0+1;
    }
    now-=(w0+1)*(s.at(1).size());

    now+=w0;
  }
  cout << ans;
}

/// confirm df==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 std;
using namespace __gnu_pbds;

#define ll long long 
#define FI first 
#define SE second
#define pb push_back 
#define eb emplace_back
#define mod 1000000007
#define all(c) (c).begin(),(c).end()
#define LB  lower_bound
#define UB  upper_bound
#define max3(a,b,c) max(c,max(a,b))
#define min3(a,b,c) min(c,min(a,b))
#define mems(s, n) memset(s, n, sizeof(s))
#define NINF INT_MIN 
#define INF INT_MAX 
#define int ll int
#define OOK order_of_key  //no of elements less than
#define FBO find_by_order //iterator pointing kth element;indexing starts from 0
#define CK3(x,y,z) cout<<(x)<<" "<<(y)<<" "<<(z)<<endl
#define CK4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<endl

typedef pair<int,int> PII;
typedef pair<pair<int,int>,int> PPII;
typedef map<int,int>MII;
typedef vector<int> VI;
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

/*int power(int a, int b)
{int x=1,y=a;while(b>0){if(b%2){x =(x*y)%mod;}y =(y*y)%mod;b/=2;}return x%mod;}
*/
//int modInverse(int a, int m) {return power(a, m-2);} //gcd(a,m)=1 
//int root(int x){return x==f[x]?x:f[x]=root(f[x]);}


signed main()
{
ios::sync_with_stdio(false); cin.tie(0);
int T=1,T1=0;//cin>>T;
while(T1++<T)
{
   int n,a,b;
   cin>>n>>a>>b;
   cout<<(n/(a+b))*a+min(a,n%(a+b))<<endl;
}


return 0;
}





Measured memory_bytes: 256
#![allow(non_snake_case, unused)]
use std::cmp::*;
use std::collections::*;
use std::f64::consts::*;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        grid: [[i64; 3]; 3],
    }
    let mut a = vec![0i64; 3];
    let mut b = vec![0i64; 3];
    b[0] = grid[0][0];
    b[1] = grid[0][1];
    b[2] = grid[0][2];
    a[0] = 0;
    a[1] = grid[1][1] - b[1];
    a[2] = grid[2][1] - b[1];

    for i in 0..3 {
        for j in 0..3 {
            if grid[i][j] != a[i] + b[j] {
                println!("No");
                return;
            }
        }
    }
    println!("Yes",);
}


Measured memory_bytes: 4352
#include <cstdio>
using namespace std;

int main() {
  int n, k, d, a, s[110]={0};
  scanf("%d%d", &n, &k);
  for(int i=0;i<k;i++) {
    scanf("%d", &d);
    for(int j=0;j<d;j++) {
      scanf("%d", &a);
      s[a] = 1;
    }
  }
  int ans=0;
  for(int i=1;i<=n;i++) if(s[i] == 0) ans++;
  printf("%d", ans);
  return 0;
}

Measured memory_bytes: 1728
#include <stdio.h>
int main(void)
{
	int a[4][3][10]={0};
	int i, j, k;
	int n, b, f, r, v;
	scanf("%d", &n);
	for(i=0; i<n; i++){
		scanf("%d %d %d %d", &b, &f, &r, &v);
		a[b-1][f-1][r-1]+=v;
	}
	for(i=0; i<4; i++){
		for(j=0; j<3; j++){
			for(k=0; k<10; k++){
				printf(" %d", a[i][j][k]);
			}
			printf("\n");
		}
		if(i!=3){
		printf("####################\n");
		}
	}
	return 0;
}


Measured memory_bytes: 2112
import numpy as np

n = int(input())
a = [int(i) for i in input().split()]

cum_sum = np.cumsum(a)
track_min = float('inf')

for i in range(n-1):
    x = int(cum_sum[i])
    y = int(cum_sum[-1]-cum_sum[i])
    diff = abs(x-y)
    if diff<track_min:
        track_min = diff
    
print(track_min)

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

int n, m, a;

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        cin >> a;
        n -= a;
    }
    if (n < 0) cout << -1 << "\n";
    else cout << n << "\n";
}


Measured memory_bytes: 3624
import sys
input = sys.stdin.readline

import numpy as np

N,X = map(int,input().split())
B,L,U = np.array([input().split() for _ in range(N)],dtype=np.int64).T

target = (B*L).sum()

full_score = B*L + U*(X-B)
i = full_score.argsort()[::-1]
B = B[i]; L = L[i]; U = U[i]; full_score = full_score[i]
full_score_cum = full_score.cumsum()

def test(x):
    # 全部でx回勉強して、target以上の得点を得ることが可能
    q,r = divmod(x,X)
    # q科目をフルで埋めて、1科目はr点まで埋める
    q_part = np.zeros_like(B)
    if q >= 1:
        q_part[q:] = full_score_cum[q-1]
        q_part[:q] = full_score_cum[q] - full_score[:q]
    r_part = np.where(r<=B,L*r,B*L+(r-B)*U)
    return (q_part + r_part).max() >= target

left = -1
right = X*N

while left + 1 < right:
    mid = (left + right)//2
    if test(mid):
        right = mid
    else:
        left = mid

answer = right
print(answer)

Measured memory_bytes: 56208
from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n, k = map(int, input().split())
a = [int(x)-1 for x in input().split()]
ans = 0
if a[0] != 0:
    ans += 1
    a[0] = 0


# g = [[] for _ in range(n)]
# for i in range(1, n):
#     g[i].append(a[i])
#     g[a[i]].append(i)


def dfs(v, par):
    global ans
    for w in g[v]:
        if w != par:
            dfs(w, v)
            if f[w]+1 == k and v != 0:
                ans += 1
                continue
            f[v] = max(f[v], f[w]+1)
    return ans


# TLE
# f = [0]*n
# print(dfs(0, -1))


# Topological Sort (TS)をDFSの代わりとする。
g = [[] for _ in range(n)]
indeg = [0]*n
for i in range(1, n):
    g[a[i]].append(i)
    indeg[i] += 1
q = deque([0])
TS = [0]
while q:
    v = q.popleft()
    for w in g[v]:
        indeg[w] -= 1
        if indeg[w] == 0:
            TS.append(w)
            q.append(w)

f = [0]*n
for w in TS[::-1]:
    if f[w] + 1 == k and a[w] != 0:
        ans += 1
        continue
    f[a[w]] = max(f[a[w]], f[w]+1)

print(ans)


Measured memory_bytes: 104520