akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define X real()
#define Y imag()
using namespace std;
typedef double D;
typedef complex<D> P;
typedef pair<P,P> L;
typedef vector<P> Pol;
struct C{P p;D r;};
D eps=1e-9;
bool eq(D a,D b){return abs(a-b)<eps;}
int large(D a,D b){return eq(a,b)?0:(a>b?1:-1);}
bool containCC(C a,C b){
	return abs(a.p-b.p)+b.r<a.r+eps;
}
D dot(P a,P b){return real(conj(a)*b);}
P perp(L l,P p){
	D t=dot(p-l.fs,l.fs-l.sc)/norm(l.fs-l.sc);
	return l.fs+t*(l.fs-l.sc);
}
D dLP(L l,P p){return abs(perp(l,p)-p);}
Pol intCC(C a,C b){
	int x=large(abs(a.p-b.p),a.r+b.r);
	Pol ret;
	if(x==1) return ret;
	if(x==0){
		ret.pb((a.r*b.p+b.r*a.p)/(a.r+b.r));
		return ret;
	}
	if(containCC(a,b)||containCC(b,a)) return ret;
	D d=abs(a.p-b.p);
	D theta=acos((a.r*a.r+d*d-b.r*b.r)/(2.0*a.r*d));
	ret.pb(a.p+(b.p-a.p)/d*polar(a.r,theta));
	ret.pb(a.p+(b.p-a.p)/d*polar(a.r,-theta));
	return ret;
}
Pol intCL(C c,L l){
	int x=large(dLP(l,c.p),c.r);
	Pol ret;
	if(x==1) return ret;
	if(x==0){
		ret.pb(perp(l,c.p));
		return ret;
	}
	D d=dLP(l,c.p);
	if(d<eps){
		ret.pb(c.p+(l.fs-l.sc)/abs(l.fs-l.sc)*c.r);
		ret.pb(c.p-(l.fs-l.sc)/abs(l.fs-l.sc)*c.r);
		return ret;
	}
	D theta=acos(d/c.r);
	P p=perp(l,c.p);
	ret.pb(c.p+(p-c.p)/d*polar(c.r,theta));
	ret.pb(c.p+(p-c.p)/d*polar(c.r,-theta));
	return ret;
}
P p[10];
int N;
D h[10],w;
D dis(D r,D h){
	if(r<=h) return r;
	return sqrt(2*r*h-h*h);
}
void append(Pol& pol,Pol a){
	for(P p:a) pol.pb(p);
}
bool can(D r){
	D e=dis(r,w);
	if(e>=50) return 0;
	vector<L> ls;
	vector<P> ps;
	ps.pb(P(e,e));
	ps.pb(P(e,100-e));
	ps.pb(P(100-e,100-e));
	ps.pb(P(100-e,e));
	rep(i,4) ls.pb(L(ps[i],ps[(i+1)%4]));
	vector<C> cs;
	rep(i,N) cs.pb(C{p[i],dis(r,h[i])});
	rep(i,N) rep(j,i) append(ps,intCC(cs[i],cs[j]));
	rep(i,N) rep(j,4) append(ps,intCL(cs[i],ls[j]));
	for(P p:ps){
		if(e-eps<p.X&&p.X<100-e+eps&&e-eps<p.Y&&p.Y<100-e+eps){
			bool ok=1;
			rep(i,N){
				if(abs(p-cs[i].p)+eps<cs[i].r) ok=0;
			}
			if(ok) return 1;
		}
	}
	return 0;
}
int main(){
	while(true){
		cin>>N>>w;
		if(N==0) break;
		rep(i,N){
			int x,y;
			cin>>x>>y>>h[i];
			p[i]=P(x,y);
		}
		D ub=1e5,lb=0;
		rep(tt,50){
			D r=(ub+lb)/2;
			if(can(r)) lb=r;
			else ub=r;
		}
		printf("%.12f\n",ub);
	}
}

Measured memory_bytes: 3672
#include<stdio.h>


long long int dp[105][25]={};
int n;
int dat[105];

int main(void){
	
	scanf("%d",&n);
	
	int i,t1,t2,s;
	
	for(i=1;i<=n;i++){
		scanf("%d",&dat[i]);
	}
	
	for(i=0;i<=20;i++){
		dp[1][i]=0;
	}
	dp[1][dat[1]]=1;
	
	for(i=2;i<=n-1;i++){
		for(s=0;s<=20;s++){
			dp[i][s]=0;
			t1 = s + dat[i];
			if(0<=t1 && t1<=20){
				dp[i][s] += dp[i-1][t1];
			}
			t2 = s - dat[i];
			if(0<=t2 && t2<=20){
				dp[i][s] += dp[i-1][t2];
			}
		}
	}
	
	long long int ans = dp[n-1][dat[n]];
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 1048
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
	int a,b;
	cin>>a>>b;
	int t=b,count=0;
	while(t!=0)
	{
		t=t/10;
		count++;
	}
	t=a*pow(10,count)+b;
	int m=sqrt(t);
	if(m*m==t)cout<<"Yes";
	else cout<<"No";
	return 0;
}

Measured memory_bytes: 512
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
using ll=long long;
using P=pair<ll,ll>;
using PP=tuple<ll,ll,ll>;
using S=multiset<ll>;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
const ll inf=1001001001001001;
const int INF=1001001001;
const int mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
void decimal(int x){cout<<fixed<<setprecision(x);}
ll modpow(ll a,ll b){a%=mod;if(b==0)return 1;if(b&1)return a*modpow(a,b-1)%mod;ll k=modpow(a,b/2);return k*k%mod;}
vi calc(ll x){vi res;while(x>0){res.eb(x%10);x/=10;}reverse(all(res));return res;}

void solve() {
	int a,b,c;
  	cin>>a>>b>>c;
	vi v={a,b,c},v_={5,5,7};
	sort(all(v));
	if(v==v_) out("YES");
	else out("NO");
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	solve();
}


Measured memory_bytes: 256
import itertools

n,d=list(map(int,input().split()))
c=[]
for i in range(n):
    c.append(i)
l=[]
for i in range(n):
    l1=list(map(int,input().split()))
    l.append(l1)

cnt=0
for x,y in itertools.combinations(c,2):
    t=0
    for i in range(d):
        t+=(l[x][i]-l[y][i])**2
    if (t**0.5).is_integer()==True:
        cnt+=1
print(cnt)


Measured memory_bytes: 3064
def split_list(l, n):
    for idx in range(0, len(l), n):
        yield l[idx:idx + n]

def main():
    s = input()
    n = [1]
    j = 0
    for i in range(len(s)):
        if i + 1 < len(s):
            if s[i] == s[i+1]:
                n[j] += 1
            else:
                n.append(1)
                j += 1
    pairs = list(split_list(n, 2))
    ans = []
    for pair in pairs:
        a = b = 0
        sum = pair[0] + pair[1]
        if sum % 2 == 0:
            a = b = sum / 2
        elif pair[0] + 1 <= pair[1]:
            if pair[1] % 2 == 1:
                a = (sum - 1) / 2
                b = (sum + 1) / 2
            else:
                a = (sum + 1) / 2
                b = (sum - 1) / 2
        elif pair[1] + 1 <= pair[0]:
            if pair[0] % 2 == 1:
                a = (sum + 1) / 2
                b = (sum - 1) / 2
            else:
                a = (sum - 1) / 2
                b = (sum + 1) / 2
        a = int(a)
        b = int(b)
        for i in range(pair[0] - 1):
            ans.append(0)
        ans.append(a)
        ans.append(b)
        for i in range(pair[1] - 1):
            ans.append(0)
    print(' '.join([str(num) for num in ans]))

if __name__ == '__main__':
    """
    問題文
    マスの情報を表す、L と R で構成された文字列 S が与えられます。
    文字列 S の長さを N としたとき、N 個のマスが左右一列に並んでおり、左から i 番目のマスには S の左から i 番目の文字が書かれています。
    ただし、左端のマスには必ず R、右端のマスには必ず L が書かれています。
    はじめ、各マスには 1 人の子どもが居ます。

    子どもたちはそれぞれ次の規則に従った移動を 10^100 回行います。
        - 今居るマスに書かれた文字に従って 1 マス移動する。
          すなわち、今居るマスに書かれた文字が L のとき左隣のマスに、R のとき右隣のマスに移動する。

    10^100 回の移動の後に各マスに居る子どもの人数を求めてください。

    制約
    S は長さ 2 以上 10^5 以下の文字列であり、S の各文字は L または R である。S の 1 文字目は R、N 文字目は L である。
    """
    main()


Measured memory_bytes: 16452
#include<stdio.h>
char mp[2500][2500];
int dir[2500][2500][4];
int main()
{
    int h,w;
    scanf("%d%d",&h,&w);
    for(int i=0; i<h; i++)
    {
        scanf("%s",mp[i]);
    }
    for(int i=0; i<h; i++)
    {
        for(int j=0; j<w; j++)
        {
            if(mp[i][j]=='.')
            {
                dir[i][j][0]=1;
                dir[i][j][1]=1;

                if(j>0&&dir[i][j-1][0]>0)
                {
                    dir[i][j][0]=dir[i][j-1][0]+1;
                }
                if(i>0&&dir[i-1][j][1]>0)
                {
                    dir[i][j][1]=dir[i-1][j][1]+1;
                }
            }
        }
    }
    for(int i=h-1; i>=0; i--)
    {
        for(int j=w-1; j>=0; j--)
        {
            if(mp[i][j]=='.')
            {
                dir[i][j][2]=1;
                dir[i][j][3]=1;

                if(j<w-1&&dir[i][j+1][2]>0)
                {
                    dir[i][j][2]=dir[i][j+1][2]+1;
                }
                if(i<h-1&&dir[i+1][j][3]>0)
                {
                    dir[i][j][3]=dir[i+1][j][3]+1;
                }
            }
        }
    }
    int maxx=-1;
    for(int i=0; i<h; i++)
    {
        for(int j=0; j<w; j++)
        {
            if(mp[i][j]=='#') continue;
            int temp=1;
            for(int k=0; k<4; k++)
            {
//                printf("[%d k]",dir[i][j][k]);
                temp+=dir[i][j][k];
            }
//            printf("(%d temp-4)\n",temp-4);
            if(temp-4>maxx) maxx=temp-4;
        }
    }
    printf("%d\n",maxx);
    return 0;
}


Measured memory_bytes: 86144
from math import *

n = input()
x = map(float, raw_input().split())
y = map(float, raw_input().split())

for i in range(1,4):
    temp = 0
    for j in range(n):
        temp += fabs(x[j]-y[j])**i
    print pow(temp,1.0/i)

d = 0
for i in range(n):
    if(fabs(x[i]-y[i]) > d):
        d = fabs(x[i]-y[i])
print d

Measured memory_bytes: 4456
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<deque>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

int X[200010], A[200010];
int main()
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> X[i];
		A[i] = X[i];
	}
	sort(A, A + N);
	for (int i = 0; i < N; i++) {
		if (X[i] <= A[N / 2 - 1]) cout << A[N / 2] << endl;
		else cout << A[N / 2 - 1] << endl;
	}
}


Measured memory_bytes: 3712
#define LOCAL

#undef _GLIBCXX_DEBUG

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

#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
#define LLINF 1e18
#define INF (int)1e9+1

// Copied from Gennady-Korotkevich's template

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
	return '"' + s + '"';
}

string to_string(const char* s) {
	return to_string((string)s);
}

string to_string(bool b) {
	return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
	bool first = true;
	string res = "{";
	for (int i = 0; i < static_cast<int>(v.size()); i++) {
		if (!first) {
			res += ", ";
		}
		first = false;
		res += to_string(v[i]);
	}
	res += "}\n";
	return res;
}

template <size_t N>
string to_string(bitset<N> v) {
	string res = "";
	for (size_t i = 0; i < N; i++) {
		res += static_cast<char>('0' + v[i]);
	}
	return res;
}

template <typename A>
string to_string(A v) {
	bool first = true;
	string res = "{";
	for (const auto& x : v) {
		if (!first) {
			res += ", ";
		}
		first = false;
		res += to_string(x);
	}
	res += "}\n";
	return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
	return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
	return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

template <typename A, typename B, typename C, typename D, typename E>
string to_string(tuple<A, B, C, D, E> p) {
	return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + "," + to_string(get<4>(p)) + ")";
}

void debug_out() {
	cerr << endl;
}

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << to_string(H);
	debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "\n[" << #__VA_ARGS__ << "]:\n", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

// End of Gennady-Korotkevich's template 

using llong = long long;
using PII = pair<int, int>;

const llong MOD = 998244353LL;

int main() {
	IOS;
	llong a, b, c, d; cin >> a >> b >> c >> d;
	cout << max({ a * c, a * d, b * c, b * d });
}

Measured memory_bytes: 3628
#include<iostream>
#include<vector>
#include<string>
#include<array>
#include<cmath>
#include<algorithm>

int main()
{
std::vector<int> l(210, 500);
int n;
std::cin >> n;
for(int i = 0; i < 2 * n; i++){
    std::cin >> l[i]; 
}
std::sort(l.begin(),l.end());
int max = 0;
for(int i = 0; i < n; i++){
   max = max + l[2 * i];
}
std::cout << max << std::endl;
return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    long long a[87];
    cin>>n;
    a[0]=2;
    a[1]=1;
    for(int i=2;i<=n;i++)
        a[i]=a[i-1]+a[i-2];
    cout<<a[n];
}

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

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    int cnt = 1;
    for (int i=0; i<n; i++) {
        int num;
        cin >> num;
        a[i] = make_pair(num, cnt);
        cnt++;
    }
    sort(a.begin(), a.end());
    for (int i=0; i<n; i++) {
        cout << a[i].second;
        if (i == n-1) cout << endl;
        else cout << " ";
    }
}

Measured memory_bytes: 1664
#include<stdio.h>

int main(){
	int x,y,min,d;
	scanf("%d %d",&x,&y);
	do{
	
	if(x<y)min=x;
	else   min=y;
	
	if(x>y)d=x%y;
	else   d=y%x;
	
	x=min;
	y=d;
	}while(d!=0);
	
	printf("%d\n",min);
	return 0;
}

Measured memory_bytes: 592
#include <bits/stdc++.h>
 
#define rep(i,n) for(ll i=0;i<n;++i)
#define ALL(a) (a).begin(),(a).end()
 
using namespace std;
using ll  = long long;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
 
const ll MOD  = 1e9+7;
const ll LINF = 1LL << 60;
const int INF = 1e9 + 7;

int mvx[]={0, 0, -1, 1};
int mvy[]={-1, 1, 0, 0};

int main(){
    int n, w_max;
    cin >> n >> w_max;
    
    int v[n], w[n];
    rep(i, n)cin >> v[i] >> w[i];

    //dp[i][j] : 重さj以内で、i個までの品物の合計の最大値
    ll dp[n+1][w_max+1] = {};
    rep(i, n)rep(j, w_max+1){
        dp[i+1][j] = dp[i][j];

        //品物を使う時
        if(j >= w[i]){
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-w[i]] + v[i]);
        }
    }

    cout << dp[n][w_max] << endl;
}


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

#define int long long
#define For(i, a, b) for (int i = (a); i <= static_cast<int>(b); i++)
#define Forr(i, a, b) for (int i = (a); i >= static_cast<int>(b); i--)
#define rep(i, n) For(i, 0, n - 1)
#define repall(i, arr) for (auto& i : (arr))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define dump(x) cerr << #x << " = " << (x) << '\n'
#define dump2(x, y) \
    cerr << #x << " = " << (x) << " " << #y << " = " << (y) << '\n'

template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
const int INF = LLONG_MAX / 2;
constexpr int MOD = 1e9 + 7;
using P = pair<int, int>;
using vec = vector<int>;
using mat = vector<vec>;

template <typename T1, typename T2>
ostream& operator<<(ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << " " << p.second;
}
template <typename T>
void print(const vector<vector<T>> matrix) {
    repall (vec, matrix)
        print(vec);
}
template <typename T>
void print(const vector<T> vec) {
    unsigned int len = vec.size();
    rep (i, len - 1)
        cout << vec[i] << ' ';
    cout << vec[len - 1] << '\n';
}
template <typename Arg>
void print(const Arg arg) {
    cout << arg << '\n';
}
template <typename Head, typename... Args>
void print(const Head head, const Args... args) {
    cout << head << " ";
    print(args...);
}
template <typename T>
T sum_(vector<T> vec, T init = 0) {
    return std::accumulate(all(vec), T(init));
}

void yn(bool tf) { print(tf ? "Yes" : "No"); }
void YN(bool tf) { print(tf ? "YES" : "NO"); }

template <typename T>
void init(vector<T>& v) {
    rep (i, v.size())
        cin >> v[i];
}

template <typename T, typename U>
void init(vector<T>& v, vector<U>& w) {
    assert(v.size() == w.size());
    rep (i, v.size())
        cin >> v[i] >> w[i];
}

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

// -------------------------------------------------------------------
// sort 1 2 3 4
// pqr 1 2 3 must impl >

signed main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);

    int n, k;
    cin >> n >> k;
    print(k == 1 ? 0 : n - k);

    return 0;
}


Measured memory_bytes: 256
n = int(input())
count = 0
for i in range(n):
    x = int(input())
    if (x == 2):
        count += 1
    elif (x % 2 == 0):
        continue
    else:
        if (pow(2, x - 1, x) == 1):
            count += 1
print(count)
 

Measured memory_bytes: 7700
#include <iostream>
#include <cstdio>
#include <string>
#include <map>
using namespace std;

char encode(char x,int a,int b){
	return ( ( a * (x-'a') + b) % 26 ) + 'a';
}

char decode(char x, int a, int b){
	int t = ( x - 'a') - b;
	while( (t%a) != 0 ) t += 26;
	return (t/a) % 26 + 'a';
}

string encode(string s, int a, int b){
	for(int i =0 ; i<(int)s.size() ; ++i )
		if( s[i] >= 'a' && s[i] <= 'z' )
			s[i] = encode( s[i] , a , b );
	return s;
}

string decode(string s, int a, int b){
	for(int i =0 ; i<(int)s.size() ; ++i )
		if( s[i] >= 'a' && s[i] <= 'z' )
			s[i] = decode( s[i] , a , b );
	return s;
}

int main(){
	int n=1;
	int a[12] = {1,3,5,7,9,11,15,17,19,21,23,25};
	
	string str, s;
	//scanf("%d ", &n);
	cin >> n;
	getline( cin , str );
	
	for(int i=0 ; i<n ; ++i){
		bool flag = false;
		getline( cin , str );
		//char foo[257];
		//gets( foo );
		//str = foo;

		for(int i=0 ; i<12 ; ++i){
			for(int j=0 ; j<26 ; j++){
				s = decode( str , a[i] , j );
				if( s.find("this") != string::npos || s.find("that") != string::npos ){
					flag = true;
					break;
				}
			}
			if( flag ) break;
		}
		//printf("%s\n" , s.c_str() );
		cout << s << endl;
	} 
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
int main(void) {
    int n,a,sum_a=0,sum_b=0;
    std::deque<int> deq;
    cin>>n;
    for (int i=0;i<n;i++) {
        cin>>a;
        deq.emplace_back(a);
    }
    sort(deq.begin(),deq.end(),greater<int>());
    for (int j=0;j<n;j++) {
        if (j%2==0) {
            sum_a=sum_a+deq[j];
        } else {
            sum_b=sum_b+deq[j];
        }
    }
    cout<<sum_a-sum_b<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll weight[105],value[105];
ll dp[105][100005];
int main()
{
    ll n,W;
    scanf("%lld %lld",&n,&W);
    for(ll i=1;i<=n;i++){
        ll w,v;
        scanf("%lld %lld",&weight[i],&value[i]);
    }
    for(ll i=1;i<=n;i++){
        for(ll j=0;j<=100000;j++){
            dp[i][j]=1e18;
        }
    }
    for(ll i=1;i<=n;i++) dp[i][value[i]]=weight[i];
    for(ll i=2;i<=n;i++){
        for(ll j=0;j<=100000;j++){
            dp[i][j]=min(dp[i][j],dp[i-1][j]);
            if(j>=value[i]){
                dp[i][j]=min(dp[i][j],dp[i-1][j-value[i]]+weight[i]);
            }
        }
    }
    ll ans;
    for(ll i=100000;i>=0;i--){
        if(dp[n][i]<=W){
            ans=i;
            break;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 79360
#include <iostream>

using namespace std;

int main()
{
    unsigned long n{};
    cin >> n;
    unsigned long a[200005] = {};
    for (unsigned long i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    unsigned long left{}, right{n - 1}, leftSum{}, rightSum{};
    while (left <= right)
    {
        if (leftSum <= rightSum)
        {
            leftSum += a[left++];
        }
        else
        {
            rightSum += a[right--];
        }
    }
    if (leftSum < rightSum)
    {
        cout << rightSum - leftSum;
    }
    else
    {
        cout << leftSum - rightSum;
    }

    return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define deb(x) cout<<#x<<" = "<<x<<"\n";


signed main()
{
	//#ifndef ONLINE_JUDGE
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	//#endif
	/************************************/
	
	
	int n; cin>>n;
	int a[n+1], b[n];
	
	for(int &i : a) cin>>i;
	for(int &i : b) cin>>i;
	
	int sum = 0;
	for(int i : a) sum += i;
	
	for(int i=0; i<n; i++)
	{
		int temp = a[i];
		a[i] = max(a[i] - b[i], 0LL);
		b[i] = max(b[i] - temp, 0LL);
		
		temp = a[i+1];
		a[i+1] = max(a[i+1] - b[i], 0LL);
		b[i] = max(b[i] - temp, 0LL);
	}
	int temp = 0;
	for(int i : a) temp += i;

	cout<< sum - temp; 
}

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

#define ll long long int
#define Mod 1000000007

bool compare(pair<pair<string,int>,int> s1,pair<pair<string,int>,int> s2)
{
    if(s1.first.first>s2.first.first) return true;
    else if(s1.first.first==s2.first.first)
    {
        if(s1.first.second>s2.first.second) return false;
        else return true;
    }
    else return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n; cin>>n;
    vector<pair<pair<string,int>,int>>v(n);
    for(int i=0;i<n;i++)
    {
        cin>>v[i].first.first>>v[i].first.second;
        v[i].second=i+1;
    }
    sort(v.rbegin(),v.rend(),compare);
    for(int i=0;i<n;i++) cout<<v[i].second<<" ";
    return 0;
}


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

#define NDEBUG
#ifdef DEBUG
#include "../cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair


ll solve(int N, vi& a) {
    sort(ALL(a));

    int D = N-1;
    vll d(D); rep(i,D) d[i] = a[i+1] - a[i];
    vll e(D);
    for (int i=0,j=D-1,v=2; i<=j; ++i,--j,v+=2){
        e[i] = e[j] = v;
        // last
        if (i==j) e[i]--;
        else if (i+1==j){
            if (d[i] < d[j]) e[i]--;
            else e[j]--;
        }
    }
    ll ans = 0;
    rep(i,D) ans += d[i] * e[i];
    return ans;
}

int main() {
    int N; cin >> N;
    vi a(N); rep(i,N) cin >> a[i];
    cout << solve(N,a) << endl;
    return 0;
}


Measured memory_bytes: 2304
n = gets.to_i
data = n.times.map { gets.strip.split.map(&:to_i) }
r = []
cnt = 0
sum = -1000000000

(0..n-1).each do |i|
  x = data[i][0]
  t = data[i][1]
  r << [x+t, x-t]
end

r = r.sort

(0..n-1).each do |i|
  if r[i][1] >= sum 
    sum = r[i][0];
    cnt += 1;
  end
end

puts cnt

Measured memory_bytes: 25808
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long int
#define mod 1000000007

/*string solve(int n) {
        string s = "";
        if(n==0)
            return s;

        while(n)
        {
            int rem = n % 26;
            n = n/26;

            if(rem == 0)
            {
                rem = 26;
                n--;
            }
            s += ('a' + rem - 1);
        }
        reverse(s.begin(), s.end());
        return s;
    }*/

int32_t main()
 {
	//code
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t,n,w,k,x,i;
    //cin>>t;
    t=1;
    while(t--)
    {
        cin>>n;
        int A[n];
        int sum=0;
        unordered_map<int,int> m;
        for(i=0;i<n;i++)
        {
            cin>>A[i];
            m[A[i]]++;
            sum += A[i];
        }

        int q;
        cin>>q;
        while(q--)
        {
            int a, b;
            cin>>a>>b;
            sum -= a*m[a];
            sum += b*m[a];

            m[b] += m[a];
            m[a] = 0;
            cout<<sum<<endl;
        }
        m.clear();
    }

	return 0;
}

Measured memory_bytes: 7916
#include<iostream>
#include<vector>
using namespace std;

vector<bool> seen;
vector<int> fo;
vector<int> lo;
void dfs(vector<vector<int>> &g,int v,int& fp,int& lp){
    if(fo[v]==0)fo[v]=fp++;
    seen[v]=true;
    for(auto next:g[v]){
        if(seen[next])continue;
        dfs(g,next,fp,lp);
    }
    if(lo[v]==0)lo[v]=fp++;
}

int main(){
    int n;
    cin>>n;
    vector<vector<int>> g(n);
    int u,k,v;
    for(int i=0;i<n;i++){
        cin>>u>>k;
        if(k==0)continue;
        for(int j=0;j<k;j++){
            cin>>v;
            if(u==v)continue;
            g[u-1].push_back(v-1);
        }
    }

    seen.assign(n,false);
    fo.resize(n);
    lo.resize(n);
    int fp=1,lp=n+1;
    //dfs(g,0,fp,lp);
    for(int i=0;i<n;i++)dfs(g,i,fp,lp);

    for(int i=0;i<n;i++){
        cout<<i+1<<" ";
        cout<<fo[i]<<" ";
        cout<<lo[i]<<endl;
    }
    return 0;
}


Measured memory_bytes: 3144
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define REP(i, n) for(int i=0; i<=n; i++)
#define repr(i, n) for(int i=n; i>0; i--)
#define REPR(i, n) for(int i=n; i>=0; i--)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define ALL(v) v.begin(),v.end()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
template<class T> void puts(T x) { std::cout << x << std::endl; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int n, k;
ll dp[2010][2010]; // dp[i][j] = iCj

void init_nCk(int n, int k) {
    for (int i = 0; i <= n+1; i++) dp[i][0] = 1;
    for (int i = 1; i <= n+1; i++) {
        for (int j = 1; j <= n+1; j++) {
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
            dp[i][j] %= MOD;
        }
    }
}

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

    init_nCk(n, k);
    for (int i = 1; i <= k; i++) {
        cout << (dp[k-1][i-1] * dp[n-k+1][i] % MOD) << endl;
    }
}


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

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define a first
#define b second
#define sz size()
#define pb(x) push_back(x) 
#define bg begin()
#define ed end()
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define mp(x,y) make_pair(x,y)
const ll MOD=1000000007;

ll maxx(ll x,ll y,ll z){
	return max(max(x,y),z);
}
ll minn(ll x,ll y,ll z){
	return min(min(x,y),z);
}
ll gcd(ll x,ll y){
	if(x%y==0) return y;
    else return gcd(y,x%y);
}
ll lcm(ll x,ll y){
	return x*(y/gcd(x,y));
}

//a,b x
int main(){
	ll N; cin>>N;
	cout<<"ABC";
  cout<<N;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define f(a, b) for (ll i = a; i <= b; i++)
#define pb push_back
#define pf push_front
#define mp make_pair
using namespace std;
#define N 100005
const int INF = 1000000001;
const int MOD = 998244353 ; //1e9+7;

//vector< vector<ll> > g(N);
//vector< pair<ll, pair< ll, ll > > > g(N);
//ll vis[N] = {0}, par[N] = {0}, child[N] = {0}, cnt = 0;
ll dp[N] = {0}, n, a[N] = {0};

void solve(){
    cin >> n;
    f(0,n-1) cin >> a[i];
    dp[0] = 0; dp[1] = abs(a[0] - a[1]);
    f(2,n-1){
        dp[i] = min( dp[i-1] + abs(a[i] - a[i-1]), dp[i-2] + abs(a[i] - a[i-2]) );
    }
    cout << dp[n-1] << "\n";
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ll t;cin >> t;for(ll index=1; index<=t; index++){
        //cout << "Case #" << index << ": " ;
        solve();
   // }
    return 0;
}

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

#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
const int inf = 1000000001;
const ll INF = 1e16;
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<<fixed<<p<<endl;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };

#define N 102
#define M 1010
int n, m;
vector< vector< pair<int, int> > > adj(N, vector< pair<int, int> >());
vii hyou(N, vi(N, inf));


int main() {
	cin >> n >> m;
	int i, j, k;
	for (i = 0; i < n; i++) {
		hyou[i][i] = 0;
	}
	vii l(m, vi(3));
	for (i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		hyou[a - 1][b - 1] = hyou[b - 1][a - 1] = c;
		l[i][0] = a - 1;
		l[i][1] = b - 1;
		l[i][2] = c;
	}
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			for (k = 0; k < n; k++) {
				if (hyou[j][k] > hyou[j][i] + hyou[i][k]) {
					hyou[j][k] = hyou[j][i] + hyou[i][k];
				}
			}
		}
	}
	
	int ans = 0;
	for (i = 0; i < m; i++) {
		bool flag = false;
		for (j = 0; j < n; j++) {
			for (k = 0; k < n; k++) {
				if (hyou[j][k] == hyou[j][l[i][0]] + l[i][2] + hyou[l[i][1]][k]) {
					flag = true;
				}
			}
		}
		if (!flag) {
			ans++;
		}
	}
	cout << ans << endl;
}

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

int main(){
	while(1){
		int a,b,c;

		cin>>a>>b>>c;

		if(a==0&&b==0&&c==0)return 0;

		int ans=0;
		for(int i=1;i<c;i++){
			for(int j=i;j<c;j++){

				int x=i*(100+a)/100;
				int y=j*(100+a)/100;

				if(x+y!=c)continue;

				int ans1=i*(100+b)/100;
				int ans2=j*(100+b)/100;

				ans=max(ans,ans1+ans2);
			}
		}
		cout<<ans<<endl;
	}
}

Measured memory_bytes: 3076
N, M = map(int, input().split())
PY = [tuple(map(int, input().split())) for _ in range(M)]
sPY = sorted(PY, key=lambda py: (py[0],py[1]))

i = 1
bp = 1
d = {}
for p, y in sPY:
    if p != bp:
        i = 1
        bp = p
    d[y] = i
    i += 1

for p, y in PY:
    i = d[y]
    print("{0:06}{1:06}".format(p, i))

Measured memory_bytes: 33924
#include <bits/stdc++.h>
#define FOR(i,a,b)  for(int (i)=(a);(i)<(b);(i)++)
#define REP(i,n)    FOR(i,0,n)
#define RER(i,n)    FOR(i,0,(n+1))
#define pb          push_back
#define mp(a,b)     make_pair((a),(b))
#define mset(m,v)   memset(m,v,sizeof(m))
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pair<int, int> > vpii;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll,ll> pll;
typedef vector<pair<ll, ll> > vpll;
typedef vector<string> vs;
typedef long double ld;
const double EPS    = 1e-10;
const int INF       = 1e+9;
const double PI     = acos(-1);


auto main() -> int
{
    int a, b;
    cin >> a >> b;

    if ( a == 1 ) {
        a = 14;
    }
    if ( b == 1 ) {
        b = 14;
    }

    cout << ((a > b) ? "Alice" : (a < b) ? "Bob" : "Draw") << endl;

    return 0;
}



Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
  let stdin = stdin();
  let stdin = stdin.lock();
  let token: String = stdin
    .bytes()
    .map(|c| c.expect("failed to read char") as char)
    .skip_while(|c| c.is_whitespace())
    .take_while(|c| !c.is_whitespace())
    .collect();
  token.parse().ok().expect("failed to parse token")
}

fn main() {
  let n = read::<usize>();
  let m = read::<i32>();
  let mut pm: Vec<(i32, i32)> = vec![];
  let mut vec_t: Vec<Vec<i32>> = vec![vec![]; n];

  for _ in 0..m {
    let p = read::<i32>();
    let m = read::<i32>();
    pm.push((p, m));
    vec_t[(p - 1) as usize].push(m)
  }

  for i in 0..vec_t.len() {
    vec_t[i].sort();
  }

  for (p, m) in pm {
    let m_num = vec_t[(p - 1) as usize].binary_search(&m).unwrap();
    let p_num: String = format!("{:0>keta$}", p, keta = 6 as usize);
    let m_num: String = format!("{:0>keta$}", m_num + 1, keta = 6 as usize);

    println!("{}{}", p_num, m_num);
  }
}



Measured memory_bytes: 11772
// 3
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>

class Lower {
 private:
  long N;
  std::vector<long> H;
  long count = 0, current = 0;

 public:
  Lower() {
    std::scanf("%ld", &N);
    for (long i = 0; i < N; i++) {
      long b;
      std::scanf("%ld", &b);
      H.push_back(b);
    }
    for (long i = 0; i < N - 1; i++) {
      if (H.at(i) >= H.at(i + 1))
        current++;
      else {
        if (current > count)
          count = current;
        current = 0;
      }
    }
    if (current > count)
      count = current;

    std::printf("%ld\n", count);
  }
};

int main() {
  Lower l;
  return 0;
}

Measured memory_bytes: 1400
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cassert>

using namespace std;

using ll = long long;

int main() {
    int n;
    
    cin >> n;
    
    auto query = [](int i) {
        cout << i << endl;
        
        string s;
        cin >> s;
        
        if (s == "Vacant") {
            exit(0);   
        } else if (s == "Male") {
            return 0;
        } else if (s == "Female") {
            return 1;
        } else {
            assert(false);   
        }
    };
    
    pair<int, bool> l(0, 0), r(n - 1, 0);
    
    l.second = query(0);
    r.second = query(n - 1);
    
    for (int i = 0; i < 20; i++) {
        pair<int, int> m((l.first + r.first) / 2, 0);
        
        m.second = query(m.first);
        
        if (((m.first - 1 - l.first) % 2 == 0 && l.second == m.second) || ((m.first - 1 - l.first) % 2 == 1 && l.second != m.second)) {
            r = m;
        } else {
            l = m;
        }
    }
}


Measured memory_bytes: 852
#include<bits/stdc++.h>
using namespace std;
int r[1000100];
int main()
{//freopen("in.txt","r",stdin);
	int x,n;scanf("%d%d",&x,&n);
	for (int i=1;i<=n;i++) scanf("%d",&r[i]);
	int q,now=1,p=-1,low=x,high=0,ad=0;scanf("%d",&q);
	while (q--)
	{
		int t,a;scanf("%d%d",&t,&a);
		while ((now<=n)&&(t>=r[now]))
		{
			int dlt=p*(r[now]-r[now-1]);
			ad+=dlt;low=min(x,max(dlt+low,0));high=min(x,max(dlt+high,0));
			now++;p*=-1;
		}
		printf("%d\n",min(x,max(0,min(low,max(high,a+ad))+p*(t-r[now-1]))));
	}
}

Measured memory_bytes: 1536
#include<bits/stdc++.h>
int n,M,a[200005],l,r,m,i;
int calc(int l,int r){
	int mx=0;l<0?l=1:0;
	for(i=0;i<r-l+1>>1;++i)mx=std::max((a[l+i]+a[r-i])%M,mx);
	return mx;
}
int main(){
	scanf("%d%d",&n,&M);
	for(i=1;i<=n*2;++i)scanf("%d",a+i);std::sort(a+1,a+n*2+1);
	for(r=n;l<r;){
		m=l+r>>1;
		for(i=0;i<n-m;++i)if(a[m*2+1+i]+a[n*2-i]<M)break;
		if(i<n-m)l=m+1;else r=m;
	}
	printf("%d\n",std::max(calc(1,l*2),calc(l*2+1,n*2)));
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;

int main(){
    int a, b, c, x;
    cin >> a >> b >> c >> x;

    int count = 0;

    for(int i = 0; i <= a; i++){
        for(int j = 0; j <= b; j++){
            for(int k = 0; k <= c; k++){
                if(500*i + 100*j + 50*k == x){
                    count++;
                }
            }
        }
    }

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

    return 0;
}

Measured memory_bytes: 256
#[allow(unused_imports)]
use std::cmp;

fn run() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let x: usize = sc.read();
    let y: usize = sc.read();

    let mut ans = false;
    for i in 0..=x {
        let num = 2 * i + 4 * (x - i);
        if num == y {
            ans = true;
        }
    }
    if ans {
        println!("Yes");
    } else {
        println!("No");
    }
}

fn main() {
    std::thread::Builder::new()
        .name("run".into())
        .stack_size(256 * 1024 * 1024)
        .spawn(run)
        .unwrap()
        .join()
        .unwrap();
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: std::ops::Deref<Target = str>>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn read_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn read_pairs<T: std::str::FromStr>(&mut self, n: usize) -> Vec<(T, T)> {
        (0..n).map(|_| (self.read(), self.read())).collect()
    }
    pub fn read_pairs_1_indexed(&mut self, n: usize) -> Vec<(usize, usize)> {
        (0..n)
            .map(|_| (self.read::<usize>() - 1, self.read::<usize>() - 1))
            .collect()
    }
    pub fn read_chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
    pub fn read_char_grid(&mut self, n: usize) -> Vec<Vec<char>> {
        (0..n).map(|_| self.read_chars()).collect()
    }
    pub fn read_matrix<T: std::str::FromStr>(&mut self, n: usize, m: usize) -> Vec<Vec<T>> {
        (0..n)
            .map(|_| (0..m).map(|_| self.read()).collect())
            .collect()
    }
}


Measured memory_bytes: 2224
n,m= map(int,input().split())
a = [input().rstrip().split() for j in range(m)]
cnt = 0#現在の経路
# a
visited=[False]*n#もう訪問したか
graph = [[False for i in range(n)] for j in range(n)]#どこが連結されているか
# graph
for i in range(0,m):
    x = int(a[i][0])-1
    y = int(a[i][1])-1
    graph[x][y]=graph[y][x]=True
# graph
    
def DFS(v,n,visited):
    # print(visited)
    all_visited = True #bool
    for i in range(0,n):
        if(visited[i]==0):
            all_visited = False
    if(all_visited):
        return 1

    ret = 0

    for i in range(0,n):
        if(graph[v][i]==False):
            continue
        if(visited[i]):
            continue

        visited[i] = True
        ret += DFS(i,n,visited)
        visited[i] = False

    return ret
visited[0]=True
print(DFS(0,n,visited))

Measured memory_bytes: 3064
n, m = map(int, input().split())
ab = []

for i in range(n):
    ab.append(tuple(map(int, input().split())))

ab.sort()
ans = 0
num = 0
i = 0

while num < m:
    t = min(ab[i][1], m - num)
    ans += ab[i][0] * t
    num += t
    i += 1


print(ans)

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

using namespace std;

typedef long long ll;
#define inf (1ll << 60)
ll sums[(1 << 16)];
ll dp[(1 << 16)];

ll calculate(vector<vector<ll> >& score, ll mask) {

	ll ans = 0;
	for (int i = 0; i < 17; i++) {
		for (int j = i + 1; j < 17; j++) {
			if ((((mask) & (1 << i)) != 0) and (((mask) & (1 << j)) != 0)) {
				ans += score[i][j];
			}
		}
	}
	return ans;
}


void prepareSum(vector<vector<ll> >& score, ll n ) {

	for (ll p = 1; p < (1 << n); p++) dp[p] = inf;
	for (ll j = 1; j < (1 << n); j++) {
		sums[j] = calculate(score, j);
	}
}

ll solve(vector<vector<ll> >& score, ll mask) {

	if (mask == 0) return  0;
	if (dp[mask] != inf) return dp[mask];

	ll ans = 0ll;

	for (int submask = mask; submask != 0; submask = (submask - 1)&mask) {
		ans = max(ans , sums[submask] + solve(score, mask ^ submask));
	}

	return dp[mask] = ans;
}


int main() {

	ll n;
	cin >> n;



	vector<vector<ll> > score(n + 1, vector<ll>(n + 1));
	for (ll i = 0; i < n; i++)
		for (ll j = 0; j < n; j++)
			cin >> score[i][j];

	prepareSum(score, n);

	cout << solve(score, (1 << n) - 1);
	return 0;
}

Measured memory_bytes: 4644
s=input()

def dfs(i,f):
    global ans
    if i==len(s)-1:
        ans+=eval(f)
    else:
        #+を入れるかどうか
        dfs(i+1,f+'+'+s[i+1])
        dfs(i+1,f+s[i+1])

    return ans

ans=0
print(dfs(0,s[0]))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main() {
	int n;
	cin >> n;
	vector<pair<int, int>> ba(n);
	for (int i = 0; i < n; i++) {
		cin >> ba[i].second >> ba[i].first;
	}
	sort(ba.begin(), ba.end());
	ll sum = 0;
	for (int i = 0; i < n; i++) {
		sum += ba[i].second;
		if (sum > ba[i].first) {
			cout << "No";
			return 0;
		}
	}
	cout << "Yes";
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define FOR(i,a,b) for (ll i=(a);i<(ll)b; i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define INF 1000000000000000
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; }
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;
typedef pair<ll,ll> p;
constexpr int MOD = 1000000007;

void print(const std::vector<int>& v)
{
  std::for_each(v.begin(), v.end(), [](int x) {
    std::cout << x << " ";
  });
  std::cout << std::endl;
}

int H,W;
vector<string>  fi;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main(){
    cin >> H >> W;
    fi.resize(H);
    REP(i,H) cin>>fi[i];
    vector<vector<int>> dist(H,vector<int>(W,-1));//多点をスタートとして扱う
    queue<p> que;
    REP(i,H){
        REP(j,W){
            if(fi[i][j] =='#'){
                dist[i][j] = 0;
                que.push(p(i,j));
            }
        }
    }
    while(!que.empty()){
        auto cur = que.front();
        que.pop();
        for(int dir = 0; dir < 4; ++dir){
            int nx =cur.first + dx[dir];
            int ny = cur.second+ dy[dir];
            if(nx<0 || nx >= H || ny<0 || ny >= W) continue;
            if(dist[nx][ny] == -1){
                dist[nx][ny] = dist[cur.first][cur.second] + 1;
                que.push(p(nx,ny));
            }
        }
    }

    int res = 0;
    REP(i,H){
        REP(j,W){
            res = max(res,dist[i][j]);
        }
    }
    cout<<res<<endl;
}



Measured memory_bytes: 21556
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define MOD 1000000007
using Graph = vector<vector<int>>;
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;
// 任意長整数型
using Bint = mp::cpp_int;
// 仮数部が1024ビットの浮動小数点数型(TLEしたら小さくする)
using Real = mp::number<mp::cpp_dec_float<1024>>;

int main (){
  int A,B,C,K;
  cin>>A>>B>>C>>K;
  while(A>=B){
    if(K==0){
      cout<<"No";
      return 0;
    }
    K--;
    B=B*2;
  }
  while(B>=C){
    if(K==0){
      cout<<"No";
      return 0;
    }
    K--;
    C=C*2;
  }
  cout<<"Yes";
}


Measured memory_bytes: 3604
#include<iostream>
#include<iomanip>

using namespace std;

int main(){
  std::cin.tie(nullptr);                  // 標準入出力高速化
  std::ios_base::sync_with_stdio(false);  // SとS++の入出力出力を非同期
  int s;
  cin>>s;
  int a=s/100,l=s%100;
  if(a>0 && a<13){
    if(l>0 && l<13){
      cout<<"AMBIGUOUS"<<endl;
    }else{
      cout<<"MMYY"<<endl;
    }
  }else{
    if(l>0 && l<13){
     cout<<"YYMM"<<endl;
    }else{
     cout<<"NA"<<endl;
    }
  }
}

Measured memory_bytes: 256
N = int(input())
An = list(map(int, input().split()))
An.sort(reverse=True)
answer = 0
t = N-1
for i, Ai in enumerate(An):
    lim = 2
    if i==0:
        lim = 1
    for j in range(lim):
        if t > 0:
            answer += Ai
        t -= 1
print(answer)


Measured memory_bytes: 31588
// AtCoder.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//

// AtCoder.cpp : このファイルには 'main' 関数が含まれています。プログラム実行の開始と終了がそこで行われます。
//


#define _USE_MATH_DEFINES
#include<math.h>

//#include<cmath>

#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>



//#include "Ants.h"
using namespace std;
typedef long long ll;
#define rad_to_deg(rad) (((rad)/2/M_PI)*360)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i,n) for(int i=0;i<n;i++)
#define show(s) cout<<s<<endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define LINF (1000000000000000000ll)

//typedef pair < int, int> P;
ll gcd(ll a, ll b) {//最大公約数を求める///最大公倍数a*b/gcd(a,b)
	if (b == 0) return a;
	return gcd(b, a % b);
}

ll lcd(ll a, ll b) {//最小公倍数を求める　b=0のときaを返す
	if (b == 0) return a;
	return (a / gcd(a, b)) * b;
}
vector<int> divnum(ll num) {
	int dig;
	vector<int>p;
	while (num) {
		dig = num % 10;
		p.push_back(dig);
		num /= 10;
	}
	return p;
}
int keta(ll num) {
	int dig;
	vector<int>p;
	while (num) {
		dig = num % 10;
		p.push_back(dig);
		num /= 10;
	}
	return p.size();
}

ll N, K,A[200005];
int main()
{
	cin >> N >> K;
	rep(i, N) {
		cin >> A[i];
	}
	sort(A, A + N);

	ll ub = LINF, lb = -LINF;
	while (ub-lb>1) {
		ll x = (ub + lb) / 2;
		//x = -7;
		bool ok = [&]{
			ll res = 0;
			
			rep(i, N) {
				ll l = -1, r = N;
	
				if (A[i] >= 0) {
					
					while (r - l > 1) {
						ll mid = (l + r) / 2;
						if (A[i] * A[mid] < x) {
							l = mid;//use this
						}
						else {
							r = mid;
						}
						
					}
					res += r;
					
				}
				else {
					while (r - l > 1) {
						ll mid=(l + r) / 2;
						if (A[i] * A[mid] >= x) {
							l = mid;
						}
						else {
							r = mid;
						}
						
					}
					res += (N-r);
					
				}
				if (A[i] * A[i] < x)res--;
				
				
			}
			res /= 2;
			if (res < K) {
				return true;
			}
			else {
				return false;
			}
			
			
		}();
		///break;
		if (ok) {
			lb = x;
		}
		else {
			ub = x;
		}
	}
	cout << lb << endl;
	
}

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

using namespace std;

int main() {
    while (true) {
        int h, w;
        cin >> h >> w;
        if (w == 0 && h == 0) {
            break;
        }
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cout << "#";
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}



Measured memory_bytes: 3092
a, b, c, d = map(int, input().split())

amount = b - a + 1

if a % c == 0:
  c_bottom = a // c
else:
  c_bottom = a // c + 1
c_top = b // c
num_c = c_top - c_bottom + 1

if a % d == 0:
  d_bottom = a // d
else:
  d_bottom = a // d + 1
d_top = b // d
num_d = d_top - d_bottom + 1

import fractions

e = int(c * d / fractions.gcd(c, d))
if a % e == 0:
  e_bottom = a // e
else:
  e_bottom = a // e + 1
e_top = b // e
num_e = e_top - e_bottom + 1

print(amount - num_c - num_d + num_e)

Measured memory_bytes: 5104
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#define ll long long
#define rep(i, a, b) for(int i = a; i < b; i++)
using namespace std;

int main() {
  int a, b;
  cin >> a >> b;
  if(max(a,b) > 8) cout << ":(\n";
  else cout << "Yay!\n";
}

Measured memory_bytes: 3624