akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <numeric>

typedef long long ll;

template<class T> std::ostream& operator << (std::ostream& os, std::vector< T > v)
{
  for (ll i = 0; i < (ll)v.size(); i++){ os << " [" << i << "]" << v[i]; if (i % 10 == 9) os << std::endl; }
  return os;
}

template<class T, class S> std::ostream& operator << (std::ostream& os, std::map< T, S > m)
{
  ll i = 0; for (auto p : m){ os << " [" << i << "]" << p.first << "->" << p.second; i++;}
  return os;
}

template<class T> std::ostream& operator <<(std::ostream& os, std::vector< std::vector<T> > vv)
{
  for (auto& vec : vv){ os << vec; }
  return os;
}

void print(){ std::cout << std::endl; }
template<typename H> void print(H head) { std::cout << head << std::endl; }
template<typename H, typename... T> void print(H head, T... tail){ std::cout << head << " ", print(tail...); }

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

  ll N = 3;
  std::vector<ll> va(N, 0LL);
  for (ll i = 0; i < N; i++) {
    std::cin >> va[i];
  }

  ll sum = std::accumulate(va.begin(), va.end(), 0LL);
  if (sum >= 22) {
    print("bust");
  } else {
    print("win");
  }
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
int main()
{
	int x, y;
	cin >> x >> y;
	int g[] = { 99,0,2,0,1,0,1,0,0,1,0,1,0 };
	cout << (g[x] == g[y] ? "Yes" : "No");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define N 2050
#define mod 1000000007
using namespace std;
typedef long long LL;
const int tp = 4000000;

int n,k;
LL F[N][N],jc[N*N],inv[N*N],invjc[N*N];
inline int rd() {int r;scanf("%d",&r);return r;}

inline LL C(int x,int y) {
	if (x < y) return 0;
	return 1LL * jc[x] * invjc[y] % mod * invjc[x-y] % mod;
}

inline void inc(LL &x, LL y) {x=(x+y)%mod;}

int main() {
	n = rd(), k = rd();
	
	if (k == 1) {puts("1"); return 0;} 
	
	jc[0] = jc[1] = 1LL;
	for (int i=2;i<=tp;i++) jc[i] = 1LL * jc[i-1] * i % mod;
	
	inv[0] = inv[1] = 1LL;
	for (int i=2;i<=tp;i++) inv[i] = 1LL * (mod-mod/i) * inv[mod % i] % mod;
	
	invjc[0] = invjc[1] = 1LL;
	for (int i=2;i<=tp;i++) invjc[i] = 1LL * invjc[i-1] * inv[i] % mod;

	F[0][1] = 1LL;
	for (int i=2;i<=n;i++)
		F[0][i] = 1LL * F[0][i-1] * C(i*(k-1)-1, k-2) % mod;

	for (int i=1;i<=n;i++)
		for (int j=i;j<=n;j++) {
			if (i-1 >= 0) inc(F[i][j], F[i-1][j]);
			if (j-1 >= 0) inc(F[i][j], 1LL * C(i+j*(k-1)-1, k-2) * F[i][j-1] % mod);
		}

	LL ans = 1LL * F[n][n] * jc[n] % mod;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 131328
#include<bits/stdc++.h>
typedef long long     ll;
#define fast          ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fr            first
#define sc            second
#define com(i,n)      for(int i=0;i<n;i++)
#define dom(i,n)      for(int i=1;i<=n;i++)
#define mom(i,n)      for(int i=n;i>=0;i--)
#define sortI(a,n)    sort(a,a+n)
#define sortD(a,n)    sort(a,a+n,greater<int>())
#define sortvi(a)     sort(a.begin(),a.end())
#define sortvd(a)     sort(a.begin(),a.end(),greater<int>())
#define sumall(a,x)   accumulate(a.begin(),a.end(),x)
#define pi            3.14159265358979323846264338327950
using namespace std;
int main()
{
     string s;
     cin>>s;
     com(i,3)
     {
          cout << s[i];
     }
}



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

int main(){
    int money, m;

    cin >> money >> m;
    vector <int> coin(m);

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

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

    vector <int> dp(money + 1, 1e9);
    dp[0] = 0;

    for(int i = 0; i <= money; i++){
        for(int j = 0; j < m; j++){
            if(i < coin[j]){
                continue;
            }

            dp[i] = min(dp[i], dp[i-coin[j]]+1);
        }
        //printf("dp %d\n", dp[i]);
    }

    printf("%d\n", dp[money]);

    return 0;

}



Measured memory_bytes: 3280
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vii = vector<vi>;
using vs = vector<string>;
using in6 = int64_t;
using ind = double;
using pii = pair<int,int>;
using psi = pair<string,int>;
using vpi = vector<pii>;
using vps = vector<psi>;
#define rep(i, n) for (in6 i = 0; i < (in6)(n); i++)
#define repa(i,a,n) for(in6 i = a; i < (in6)(n); i++)
#define repdown(i,n) for(in6 i = n; i > 0; i--)
#define kyun ios::sync_with_stdio(false)
#define hinata cout << "\n"
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define inf 2147483647

int main() {
  kyun;
  int n;
  cin >> n;
  string s,a,b;
  cin >> s;
  a = s.substr(0,n/2);
  b = s.substr(n/2);
  if(a == b && n % 2 == 0) cout << "Yes";
  else cout << "No";
  hinata;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int NN = 1e6+10;
typedef long long ll;

int N,M;
vector<int> ve[NN];
priority_queue<int> q;
int main(){
	cin>>N>>M;
	for(int i = 1;i<=N;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		if(a>M) continue;
		ve[M-a+1].push_back(b); //表示M-a+1天之后不能做此份工作(也就是做了赚不到钱) 
	}
	ll earn = 0;
	for(int i = M;i>=1;i--){
		for(int j=0;j<ve[i].size();j++){
			int m=ve[i][j];
			q.push(m);
		}
		if(!q.empty()){
			earn += q.top();
			q.pop();
		}
	}
	cout<<earn<<endl;
	
	return 0;
}


Measured memory_bytes: 26752
#include <bits/stdc++.h>
using namespace std;
int n,a,b,c;
string s[100005];
char ans[100005];
void print(){
	cout<<"Yes"<<endl;
	for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
}
void check(){
	for(int i=1;i<=n;i++){
		if(s[i]=="AB"){
			if(a==0&&b==0){
				cout<<"No";
				exit(0);
			}
			if(a==1&&b==1&&c==0&&i!=n&&s[i+1]=="AC"){
				ans[i]='A';
				a++;
				b--;
				continue;
			}
			if(a==1&&b==1&&c==0&&i!=n&&s[i+1]=="BC"){
				ans[i]='B';
				b++;
				a--;
				continue;
			}
			if(a>b){
				ans[i]='B';
				b++;
				a--;
			}else{
				ans[i]='A';
				a++;
				b--;
			}
		}
		if(s[i]=="AC"){
			if(a==0&&c==0){
				cout<<"No";
				exit(0);
			}
			if(a==1&&b==0&&c==1&&i!=n&&s[i+1]=="AB"){
				ans[i]='A';
				a++;
				c--;
				continue;
			}
			if(a==1&&b==0&&c==1&&i!=n&&s[i+1]=="BC"){
				ans[i]='C';
				c++;
				a--;
				continue;
			}
			if(a>c){
				ans[i]='C';
				c++;
				a--;
			}else{
				ans[i]='A';
				a++;
				c--;
			}
		}
		if(s[i]=="BC"){
			if(b==0&&c==0){
				cout<<"No";
				exit(0);
			}
			if(a==0&&b==1&&c==1&&i!=n&&s[i+1]=="AB"){
				ans[i]='B';
				b++;
				c--;
				continue;
			}
			if(a==0&&b==1&&c==1&&i!=n&&s[i+1]=="AC"){
				ans[i]='C';
				c++;
				b--;
				continue;
			}
			if(b>c){
				ans[i]='C';
				c++;
				b--;
			}else{
				ans[i]='B';
				b++;
				c--;
			}
		}
	}
	print();
}
int main(){
	cin>>n>>a>>b>>c;
	for(int i=1;i<=n;i++) cin>>s[i];
	check();
	return 0;
}

Measured memory_bytes: 6876
#include <stdio.h>


int main(void)
{
	int j,n;
	while(scanf("%d",&j)!=EOF){
	n=j%39;
	if(n==0){
		printf("3C39\n");
	}
	else if(n<=9){
		printf("3C0%d\n",n);
	}
	else{
	printf("3C%d\n",n);
	}
	}
	
	return 0;
}

Measured memory_bytes: 608
in1 = input().split()
in2 = input().split()
in3 = input()
oni = int(in1[0])
onispeed = int(in1[1])
kid = int(in2[0])
kidspeed = int(in2[1])
time = int(in3)
pase = onispeed - kidspeed
flg = True #正の方向
if kid - oni < 0:
  flg = False #負の方向

if flg:
  oniend = (pase * time) + oni
  if (pase <= 0) or (oniend < kid):
    print("NO")  
  else:
    print("YES")
else:
  oniend = oni - (pase * time)
  if (pase <= 0) or (oniend > kid):
    print("NO")  
  else:
    print("YES")


Measured memory_bytes: 9080
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<map>
#include <algorithm>
#include<cstdlib>
#include<cmath>
#include<deque>
#include <numeric>
#include<valarray>
typedef unsigned long long ull;
typedef  long long ll;


int main() {
	ll  n , m , c;

	std::cin >> n >> m >> c;

	std::vector<int> bm(m);

	for (int i = 0; i < m; i++)
	{
		std::cin >> bm[i];
	}
	int outcount = 0;
	for (int j = 0; j < n; j++) {
		std::vector<int> am(m);
		for (int i = 0; i < m; i++)
		{
			std::cin >> am[i];
		}
		ll tmpans = 0;
		tmpans = std::inner_product(am.begin(), am.end(), bm.begin(), c);
		if (tmpans > 0) outcount += 1;
	}
	std::cout << outcount << std::endl;

	return 0;
}

Measured memory_bytes: 256
n, m = map(int, input().split())
x = [-1] * (n+1)
for _ in range(m):
    a, b = map(int, input().split())
    x[b] = max(x[b], a)
ans = 0
bmx = 0
for i in range(n+1):
    if bmx <= x[i]:
        ans += 1
        bmx = i
print(ans)

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

int main(){
    long long n;
    cin >> n;
    vector<long long> c(n-1);
    vector<long long> s(n-1);
    vector<long long> f(n-1);

    for(long long i = 0; i < n-1; i++) cin >> c[i] >> s[i] >> f[i];

    for(long long i = 0; i < n; i ++){
        long long t = 0;
        for(long long j = i; j < n-1; j++){
            if(t < s[j]) t = s[j];
            else if(t % f[j] == 0);
            else t = t + f[j] - t%f[j];

            t += c[j];
        }
        printf("%lld\n", t);
    }
    return 0;
}

Measured memory_bytes: 3708
//#include "pch.h"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <limits.h>
#include <string>
#include <deque>
#include <cmath>
#include <bitset>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

#define rip(i, n, s) for (int i = (s);i < (int)( n ); i++)
#define mpa make_pair
#define all(a)

int main(){
	ll n;cin >> n;
	if(n%2){
		cout << 0 << endl;
		return 0;
	}
	n /=2;
	ll ans = 0;
	while(n){
		ans += n/5;
		n /= 5;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mod 1000000007
ll exp(ll taban, ll us) {
    ll carpan = taban % mod;
    ll temp = us;
    ll res = 1;
    while(temp){
        if(temp % 2) res = (res*carpan) % mod;
        temp /= 2;
        carpan = (carpan*carpan) % mod;
    }
    return res;
}
ll ebob(ll a, ll b){
	if(!a)return b;
	return ebob(b%a, a);
}
ll ekok(ll a, ll b){
	return (a*b)/ebob(a, b);
}
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	string s; cin>>s;
	bool c = 1;
	int n = s.size();
	for(int i = 0; i < n; i++){
		if(s[i] != s[n-1-i]){
			c = 0;
			break;
		}
	}
	for(int i = 0; i < n/2; i++){
		if(s[i] != s[n/2-1 - i]){
			c = 0; break;
		}
	}
	for(int i = n/2+1; i < n; i++){
		if(s[i] != s[n + n/2 - i]){
			c = 0;
			break;
		}
	}
	c ? cout<<"Yes" : cout<<"No";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sqr(x) ((x)*(x))
#define mp make_pair
#define uint unsigned
#define PI pair<int,int>
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read(){
	int x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(int a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(int a){
    if(a<0){
    	a=-a; putchar('-');
	}
	write(a); puts("");
}
inline int rnd(int x){
	return (rand()<<16|rand())%x;
}
const int N=100005;
int n;
vector<int> v[N];
int dfs(int p,int fa){
	//if(fa)cout<<p<<" "<<*lower_bound(v[p].begin(),v[p].end(),fa)<<" "<<fa<<endl;
	int sum=0;
	for(unsigned i=0;i<v[p].size();i++)if(v[p][i]!=fa){
		sum^=dfs(v[p][i],p)+1;
	}
	//cout<<p<<" "<<sum<<endl;
	return sum;
}
int main(){
	n=read();
	for(int i=1;i<n;i++){
		int s=read(),t=read();
		v[s].push_back(t); v[t].push_back(s);
	}
	puts(dfs(1,0)?"Alice":"Bob");
}

Measured memory_bytes: 11904
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n;i>0;i--)
#define rep1(i,s,n) for(int i=s;i<n;i++)
#define max0(a,b,c) max(max(a,b),c)
#define min0(a,b,c) min(min(a,b),c)
#define ft first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
using namespace std;
using Graph = vector<vector<int>>;
typedef long long lint;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldouble;
typedef vector<int> vec;
typedef vector<ll> lvec;
typedef vector<ull> ulvec;
typedef vector<pair<int,int>> pvec;
typedef vector<pair<ll,ll>> plvec;
typedef vector<tuple<ll,ll,ll>> tvec;
typedef vector<string> svec;

ll f(ll n){
    if(n==1) return 1;
    return n*f(n-1);
}

int main(){
    ll n;
    cin>>n;
    lvec x(n),y(n);
    rep(i,n) cin>>x[i]>>y[i];
    double sum=0;
    rep(i,n-1){
        for(int j=i+1;j<n;j++) sum+=2*f(n-1)*sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2));
    }
    printf("%.10f",sum/f(n));
}

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007LL

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    ll N;
    cin >> N;
    vector<array<ll, 10>> F(N);
    vector<array<ll, 11>> P(N);
    rep(i, N) {
        rep(j, 10) cin >> F[i][j];
    }
    rep(i, N) {
        rep(j, 11) cin >> P[i][j];
    }
    ll ans = numeric_limits<ll>::min();
    rep2(i, 1, 1LL << 10) {
        ll temp = 0;
        rep(j, N) {
            ll tmp = 0;
            rep(k, 10) {
                if((i >> (9 - k)) & 1 == F[j][k]) tmp++;
            }
            temp += P[j][tmp];
        }
        ans = max(ans, temp);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define pf push_front
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define SZ(x) (int)(x).size()
#define ft front()
#define bk back()
#define endl '\n'
#define FOR(a, b, c) for (auto(a) = (b); (a) < (c); ++(a))
#define ROF(a, b, c) for (auto(a) = (b); (a) > (c); --(a))
#define F0R(a, b) FOR ((a), 0, (b))
#define R0F(a, b) ROF ((a), (b), -1)
#define CEIL(a, b) ((a) + (b)-1) / (b)
#define SET(a, b) memset((a), (b), sizeof(a))
template <class t>
bool ckmin(t& a, const t& b) {
    return a > b ? a = b, true : false;
}
template <class t>
bool ckmax(t& a, const t& b) {
    return a < b ? a = b, true : false;
}
#ifndef DEBUG
#define DEBUG 0
#endif
#define dout \
    if (DEBUG) std::cerr
#define dvar(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
template <class a, class b>
ostream& operator<<(ostream& o, const pair<a, b>& p);
template <class T>
struct IsC {
    template <class C>
    static char test(typename C::const_iterator*);
    template <class C>
    static int test(...);
    static const bool value = sizeof(test<T>(0)) == sizeof(char);
};
template <>
struct IsC<string> {
    static const bool value = false;
};
template <class C>
typename enable_if<IsC<C>::value, ostream&>::type operator<<(ostream& o,
                                                             const C& c) {
    o << '[';
    for (auto it = c.begin(); it != c.end();)
        o << *it << (++it != c.end() ? ", " : "");
    return o << ']';
}
template <class a, class b>
ostream& operator<<(ostream& o, const pair<a, b>& p) {
    return o << '(' << p.fi << ", " << p.se << ')';
}

typedef long double ld;

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

    int n;
    cin >> n;
    vector<ld> ps(n);
    for (auto& p : ps) cin >> p;

    vector<vector<ld>> dp(n + 1, vector<ld>(n));
    dp[0][0] = 1 - ps[0];
    FOR (i, 1, n)
        dp[0][i] = dp[0][i - 1] * (1 - ps[i]);
    dp[1][0] = ps[0];
    FOR (i, 1, n + 1) {
        FOR (j, 1, n) {
            dp[i][j] = dp[i][j - 1] * (1 - ps[j]);
            dp[i][j] += dp[i - 1][j - 1] * ps[j];
        }
    }
    // for (auto& v : dp) {
    //     for (ld d : v) {
    //         cout << setw(7) << d;
    //     }
    //     cout << endl;
    // }
    ld sum = 0;
    FOR (i, n / 2 + 1, n + 1)
        sum += dp[i][n - 1];

    cout << fixed << setprecision(12) << sum << endl;

    return 0;
}


Measured memory_bytes: 141056
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
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; }

const int mod=1000000007;
const int INF=1001001001;

vector<pair<int64_t,int64_t>>prime_factorize(int64_t x){
  vector<pair<int64_t,int64_t>>p;
  for(int64_t i=2;i*i<=x;i++){
    int cnt=0;
    if(x%i==0){
    while(x%i==0){cnt++;x/=i;}
    p.push_back(make_pair(i,cnt));
    }
  }
  if(x!=1){p.push_back(make_pair(x,1));}
  return p; 
}

int main() {
  int N;
  cin>>N;
  map<int,int>k;
  for(int i=2;i<=N;i++){
    int cur=i;
    for(int j=2;j*j<=cur;j++){
      while(cur%j==0){k[j]++;cur/=j;}
    }
    if(cur!=1){k[cur]++;}
  }
  map<int64_t,int64_t>num;
  for(auto c:k){
    if (c.second >= 74) num[74]++;
		if (c.second >= 24) num[24]++;
		if (c.second >= 14) num[14]++;
		if (c.second >= 4)  num[4]++;
		if (c.second >= 2)  num[2]++;
  }
  cout<<num[74]+num[24]*(num[2]-1)+(num[4]-1)*num[14]+num[4]*(num[4]-1)/2*(num[2]-2)<<endl;
  return 0;  
}

Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll arr[200009];
int main()
{
    ll n,t,m,x,y,i,j,k,maxi = INT_MIN,mini = INT_MAX,flag =0,sum=0;
    vector<ll>vi;
    map<ll,ll>mp;
    map<ll,ll> :: reverse_iterator it;
    cin>>n;
    for(i = 0 ;i<n ;i++)
    {
        cin>>x;
        mp[x]++;
    }
    for(it =mp.rbegin(); it!=mp.rend() ; it++)
    {
        if(flag == 0 && it->second>3)
        {
            flag = 2;
            x= it->first;
            y = it->first;
            break;
        }
        if(it->second>1){
            flag++;
        if(flag == 1)
            x= it->first;
        if(flag ==2)
        {
            y = it->first;
            break;
        }
        }
    }
    if(flag == 2)
    cout<<x*y<<endl;
    else
        cout<<0<<endl;
    return 0;

}



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

#define rep(i, n) for(int i = 0; i < (n); i++)

using namespace std;
using lint = long long;

int main(void)
{
   lint A, B, K;
   cin >> A >> B >> K;
   if(A + B <= K){
       cout << 0 <<" " << 0 << endl;
   }
   else if(A <= K){
       cout << 0 << " " << B-(K-A) << endl;
   }
   else if(A > K){
       cout << A - K << " " << B << endl;
   }
    return 0;
}

Measured memory_bytes: 256
# Aizu Problem CGL_3_C: Polygon-Point-Containment
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


def cross_product_test(A, B, C):
    if A[1] == B[1] == C[1]:
        if B[0] <= A[0] <= C[0] or C[0] <= A[0] <= B[0]:
            return 0
        else:
            return 1
    if B[1] > C[1]:
        B, C = C[:], B[:]
    if A[1] == B[1] and A[0] == B[0]:
        return 0
    if A[1] <= B[1] or A[1] > C[1]:
        return 1
    delta = (B[0] - A[0]) * (C[1] - A[1]) - (B[1] - A[1]) * (C[0] - A[0])
    if delta > 0:
        return -1
    elif delta < 0:
        return 1
    else:
        return 0

def point_in_polygon(polygon, point):
    t = -1
    polygon.append(polygon[0])
    for i in range(len(polygon) - 1):
        t *= cross_product_test(point, polygon[i], polygon[i+1])
    return t

N = int(input())
P = [[int(_) for _ in input().split()] for __ in range(N)]
Q = int(input())
for q in range(Q):
    x, y = [int(_) for _ in input().split()]
    print(point_in_polygon(P, [x, y]) + 1)

Measured memory_bytes: 7776
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <numeric>
#include <functional>
#include <array>
#include <map>
#include <set>

#define INF 1000000007 //1000000000000000003
#define MOD 1000000007

#define ll long long

//printf("%.10f", );
//cout << fixed << setprecision(10) << heikin << endl;

using namespace std;
using P = pair<int, int>;
using T = tuple<int, int, int>;
using edge = struct { int to; long long dist; };

vector<edge>tree[100010];
vector<P> connect[100005];
long long cost[100005];

int dp[50][500][500];

bool compare_by_second(pair<int, int> a, pair<int, int> b) {
	if (a.second != b.second) {
		return a.second < b.second;
	}
	else {
		return a.first < b.first;
	}
}

int main() {

	int N, MA, MB;
	cin >> N >> MA >> MB;

	vector<int>a(N);
	vector<int>b(N);
	vector<int>c(N);

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


	for (int i = 0; i <= 49;++i) {
		for (int j = 0; j <= 499;++j) {
			for (int k = 0; k <= 499;++k) {
				dp[i][j][k] = INF;
			}
		}
	}

	dp[0][0][0] = 0;
	for (int i = 0; i < N;++i) {
		for (int j = 0; j <= 400;++j) {
			for (int k = 0; k <= 400;++k) {
				if (dp[i][j][k] == INF)continue;
				dp[i + 1][j][k] = min(dp[i + 1][j][k], dp[i][j][k]);
				dp[i + 1][j + a[i]][k + b[i]] = min(dp[i + 1][j + a[i]][k + b[i]], dp[i][j][k] + c[i]);
			}
		}
	}

	int ans = INF;
	for (int i = 1; i <= 400; ++i) {
		for (int j = 1; j <= 400; ++j) {
			if (i * MB == j * MA)ans = min(ans, dp[N][i][j]);
		}
	}
	ans = ans == INF ? -1 : ans;

	cout << ans << endl;
}

Measured memory_bytes: 54528
import itertools
n,m=map(int,input().split())
node=[[0 for i in range(n)] for j in range(n)]
for i in range(m):
  a,b=[int(x)-1 for x in input().split()]
  node[a][b]=1
  node[b][a]=1
ct=0
for order in itertools.permutations(range(n),n):
  if order[0]==0:
    for j in range(n):
      if j==n-1:
        ct+=1
        break
      if not node[order[j]][order[j+1]]:
        break
    
print(ct)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001
#define mod 1000000007
#define pi 3.141592653589793
#define all(v) v.begin(),v.end()


ll gcd(ll a,ll b){
    if(b>a) swap(a,b);
    if(b==0) return a;
    return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    ll g=gcd(a,b);
    return a/g*b;
}
ll rep_jijo(ll n,ll x){
    if(x==0) return 1;
    if(x%2==0){
        ll t=rep_jijo(n,x/2);
        return t*t%mod;
    }
    return n*rep_jijo(n,x-1)%mod;
}
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};
 
int main(){
    ll n,k;
    cin >> n >> k;
    combination c(n);
    ll zero=min(n-1,k);
    mint ans;
    for(ll i=0;i<=zero;i++){
        ans+=c(n,i)*c(n-1,i);
    }
    cout << ans.x << endl;
    return 0;
}


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

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;

#define REP(i, n, m) for(ll i=n; i<(ll)m; ++i)
#define IREP(i, n, m) for(ll i=n-1; i>=m; --i)
#define rep(i, n) REP(i, 0, n)
#define irep(i, n) IREP(i, n, 0)
#define all(v) v.begin(), v.end()

int main(){
    ll n;
    cin >> n;
    cout << setprecision(16) << (double)((n+1)/2)/n << endl;
}


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

using namespace std;

typedef long long ll;

int prime(ll x){
	for(int i=2;i*i<=x;i++){
		if(x%i==0){
			return 0;
			break;
		}
	}
	return 1;
}

int main(){
	ll x;
	cin >> x;
	ll p = x;
	while(!prime(p)){
		p++;
	}
	cout << p << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int b, k;
    cin >> b >> k;
    int n[b], r[b];
    for(int i = 0; i < b; i++)
    {
    	cin >> n[i];
    	r[i] = 1000000000;
	}
	r[0] = 0;
	for(int i = 1; i < b; i++)
	{
		for(int j = i-1; j >= max(i-k, 0); j--)
		{
			r[i] = min(r[i], r[j] + abs(n[i] - n[j]));
		}
	}
	cout << r[b-1] << endl;
}



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

#define _USE_MATH_DEFINES
#define reb(i,b,n)         for(int i=(int)(b); i<(int)(n); i++)
#define rep(i,n)           reb(i,0,n)
#define each(it,v)         for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define reach(it,v)        for(__typeof((v).rbegin()) it=(v).rbegin();it!=(v).rend();it++)
#define vsort(v)           sort((x).begin(), (x).end()
#define rvsort(v)          sort((x).rbegin(), (x).rend()
#define mp(a, b)           make_pair(a, b)
#define fi                 first
#define se                 second
#define pb                 push_back
#define dbg(x)             cerr<<__LINE__<<": "<<#x<<" = ["<<(x)<<"]"<<endl;
#define dbgArr(table, n)   rep(i,n){cout<<table[i]<<' ';}cout<<'\n';
#define dbg2Arr(table,W,H) rep(y,H){rep(x,W)cout<<table[y][x]<<' ';cout<<'\n';}

using namespace std; using std::stringstream;

typedef long long       ll; typedef unsigned long long ull; typedef long double     ld;
typedef pair <int, int> P;  typedef pair <int, P>      PP;
typedef vector<int>     vi; typedef vector<vi>         vvi; typedef vector<ll>      vl;
typedef vector<P >      vP; typedef vector<char>       vc;  typedef vector<string>  vs;

static const int    INF  = 0x3f3f3f3f;
static const ll     INFL = 0x3f3f3f3f3f3f3f3fLL;
static const double EPS  = 1e-9;
static const ll     MOD  = 1000000007LL;

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

int main(int argc, char *argv[])
{
    string S, T;
    cin >> S >> T;

    bool ans = false;
    rep(i, 26) {
        string tmp = S;
        tmp += 'a'+i;

        if (T == tmp) {
            ans = true;
        }
    }

    if (ans) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 3628
deck = {"S":[0]*13, "H":[0]*13, "C":[0]*13, "D":[0]*13} 

n = input()

for i in range(0, n):
    suit, num = raw_input().split(" ")
    deck[suit][int(num)-1] = 1

for i in ["S", "H", "C", "D"]:
    for j in range(0, 13):
        if (deck[i][j] == 0):
            print("%s %d" % (i, j+1))

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

const int N=100005;
int dp[N]; int n; int arr[N];
int INF=10000000000000000;

int go(int index){
	if(index==n-1)
	return 0;
	
	if(dp[index]!=-1)
	return dp[index];
	
	int ans2=INF;
	int ans1=abs(arr[index+1]-arr[index])+go(index+1);
	if(index<n-2)
	ans2=abs(arr[index+2]-arr[index])+go(index+2);
	ans1=min(ans1,ans2);
	
	return dp[index]=ans1;
	
}

#undef int
int main(){
	#define int long long int
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t=1;
	while(t--){
		cin >> n;
		for(int i=0;i<n;i++){
			cin>>arr[i];
		}
		memset(dp,-1,sizeof(dp));
		cout<<go(0)<<endl;
	}
	return 0;
}


Measured memory_bytes: 4992
/*
    CP Submission
*/

#include<bits/stdc++.h>

using namespace std;

/* Shortcuts */
#define MP make_pair
#define PB push_back
#define ALL(x) x.begin(), x.end()
#define VAL(x) cout << #x << ": " << (x) << endl;
#define LOG(x) cout << (x) << endl;
#define SZ(x) (int)(x.size())
#define REP(i, a, b) for(int i = a; i < b; i++)

/* typedefs */
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<string,int> si;
typedef pair<int,ii> iii;
typedef vector <si> vsi;
typedef vector <ii> vii;
typedef vector <int> vi;
typedef vector <vi> vvi;
typedef vector <char> vc;
typedef vector <string> vs;
typedef map <string,vs> msvs;
typedef map <string,int> msi;
typedef map <string,string> mss;

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin>>n;

    vi ht;

    int h;

    REP(i,0,n){
        cin>>h;
        ht.PB(h);
    }


    vi dp(n, -1);

    dp[n-1] = 0;
    dp[n-2] = abs(ht[n-1] - ht[n-2]);

    for(int i = n - 3; i >= 0; i--){
        dp[i] = min(abs(ht[i] - ht[i+1]) + dp[i+1], abs(ht[i] - ht[i+2]) + dp[i+2]);
    }

    LOG(dp[0]);

    return 0;
}


Measured memory_bytes: 1144
#include <iostream>
#include <stdio.h>
#include <string>

using namespace std;

int main() {
  int N, A, B;
  cin >> N >> A >> B;
  int res = 0;
  for (int i = 1; i <= N; ++i) {
    string s = to_string(i);
    int t = 0;
    for (int j = 0; j < s.size(); ++j) {
      t += s[j] - '0';
    }
    if (A <= t && t <= B) {
      res += i;
    }
  }
  printf("%d\n", res);
}

Measured memory_bytes: 3180
#include <bits/stdc++.h>
using namespace std;
#define ll          long long int
#define pb          push_back
#define pll         pair<ll,ll>
#define pq          priority_queue
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mod         1000000007
#define inf         1000000000000000000LL
#define vl          vector<ll>
#define vll         vector<pll>
#define f           first
#define s           second
#define db          long double
#define sz(x)       (ll)x.size()
#define fix(n)      cout<<fixed<<setprecision(n)
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define all(x)      x.begin(),x.end()
#define mset(x)     memset(x,0,sizeof x)
#define pi          3.14159265358979323
ll v[100005],k,n;
//ll dp[100005];
ll c1(ll a, ll b)
{
    if(a%b==0) return (a/b)-1;
    else return (a/b);
}
bool check(ll m)
{   ll s=0;
    for(int i=1;i<n;i++)
        s+=c1(v[i]-v[i-1],m);
    return s<=k;
}
bool ispalindrome(string s2)
{
    ll n=s2.size();
    ll l=0,h=n-1;
    while(h>=l)
        if(s2[l++]!=s2[h--]) return 0;
    return 1;
}
void solve()
{
 ll t,b,m;
 string s1;
 cin>>n;
 vector<ll> pref(n+1);
 vector<ll> v2(n+1);
 for(int i=1;i<=n;i++)
    {cin>>v2[i];pref[v2[i]]++;}
ll ans=0;
for(int i=1;i<=n;i++) ans+=(pref[i]*(pref[i]-1))/2;
for(int i=1;i<=n;i++)
    {
        if(pref[v2[i]]>1) cout<<ans-(pref[v2[i]]-1)<<"\n";
        else cout<<ans<<"\n";
    }
    }   

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



Measured memory_bytes: 5760
#include<iostream>
using namespace std;
int main()
{
    string s,t;
    cin>>s;
    cin>>t;
    int l1,l2,i,ma=100000,j,c=0,k;
    l1=s.length();
    l2=t.length();
    for(i=0;i<=l1-l2;i++)
    {
        k=i;
        for(j=0;j<l2;j++)
        {
            if(s[k]!=t[j])
            {
                c++;
            }
            k++;
        }
        ma=min(ma,c);
        c=0;
    }
    cout<<ma<<endl;
    return 0;
}


Measured memory_bytes: 3628
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		StringBuilder sb = new StringBuilder();
		Set<Integer> set1 = new TreeSet<>();
		Set<Integer> set2 = new HashSet<>();
		for (int i = 0; i < n; i++) {
			set1.add(sc.nextInt());
		}
		int m = sc.nextInt();
		for (int i = 0; i < m; i++) {
			set2.add(sc.nextInt());
		}
		set1.retainAll(set2);
		for (int num : set1) {
			sb.append(num);
			sb.append('\n');
		}
		System.out.print(sb.toString());
	}
}



Measured memory_bytes: 164884
#include <stdio.h>
#include <string.h>
#include <ctype.h>
int main(){
    //カードの現状とシャッフル後
    char text[201],fin[201];
    int n,shu;
    int j;
    while(1){
        //対象文字列とシャッフル回数の読み込み
        scanf("%s %d",text,&n);
        if(!strcmp(text,"-")) break;
        
        for(int i=0;i<n;i++){
            scanf("%d", &shu);
            for(j=shu; text[j]!='\0'; j++){
                fin[j-shu] = text[j];
                
            }
            
            for(int k=0; k < shu; k++){
                fin[j-shu+k] = text[k];
                
            }
            
            for(j=0; text[j]!='\0'; j++){
                text[j] = fin[j];
                
            }
            
        } 
        printf("%s\n",text);
    }
}


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

typedef long long lint;
typedef pair<int, int> P;
#define REP(i, x, n) for(int i = x ; i < n ; ++i)
#define rep(i, n) REP(i, 0, n)
#define repr(i, n) for(int i = n - 1 ; i >= 0 ; --i)
#define ALL(x) (x).begin(), (x).end()
#define SORT(x) sort(ALL(x))

const int IINF = 1e9 + 10;
const lint LLINF = (lint)1e18 + 10;
const lint MOD = (lint)1e9 + 7;
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy8[] = {0, -1, -1, -1, 0, 1, 1, 1};

struct city{
    lint p, y;
    int id;
    
    bool operator<(const city &right) const {
        return y < right.y;
    }
};

int main(){
    int n, m;
    cin >> n >> m;
    vector<city> c(m);
    rep(i, m){
        cin >> c[i].p >> c[i].y;
        c[i].id = i;
    }
    SORT(c);
    vector<lint> ans(m), now(n+1, 1);
    rep(i, m){
        city t = c[i];
        ans[t.id] = t.p * 1000000LL + now[t.p];
        ++now[t.p];
    }
    rep(i, m){
        cout << setfill('0') << setw(12) << right << ans[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 5376
H, W = map(int, input().split())
S = []
for i in range(H):
    S.append(input())
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            continue
        count = 0
        for xs, ys in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            if i + ys < 0 or i + ys >= H or j + xs < 0 or j + xs >= W:
                break
            pos_x = j + xs
            pos_y = i + ys
            if S[i][j] == "#" and S[pos_y][pos_x] == ".":
                count += 1
        if count == 4:
            print("No")
            exit()
print("Yes")

Measured memory_bytes: 40048
#include<iostream>
using namespace std;
int main()
{
  int a,i,c=0;
  cin>>a;
 // if(a>81)
   // cout<<"No";
  for(i=1;i<=9;i++)
    if(a%i==0&&(a/i)<10)
      c=1;
   if(c==1)
    cout<<"Yes";
  else
    cout<<"No";
}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);	
   
	int n;
	cin >> n;
	vector<int> ar(n), sm(n, 0);
	for (int i = 0; i < n; i++) {
		cin >> ar[i];
	}
	sm[n - 1] = 0;
	for (int i = n - 2; i >= 0; i--) {
		if(ar[i] >= ar[i + 1])
			sm[i] = 1 + sm[i + 1];
		else
			sm[i] = 0;
	}
	cout << *max_element(sm.begin(), sm.end());
    return 0;
} 

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define all(a) a.begin(),a.end()
#define pb push_back
#define mp make_pair
const int N = 100005;
int n,q;
int a[N];
ll sum;
int freq[N];
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        scanf("%d",a+i);
        sum+=a[i];
        freq[a[i]]++;
    }
    cin>>q;
    for(int b,c,i=0;i<q;i++){
        scanf("%d%d",&b,&c);
        sum+=(c-b)*freq[b];
        freq[c]+=freq[b];
        freq[b]=0;
        cout<<sum<<endl;
    }
}


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

using namespace std;

const int N=5000;
char s[N+5];
int n,v[N+5],k;

int sol[N+5],mom[N+5];
bool viz[7][N+5];

bool sch()
{
    int mi=min(sol[0],mom[0]);
    for(int i=1;i<=mi;i++)
    {
        if(sol[i]<mom[i])
            return 0;
        if(mom[i]<sol[i])
            return 1;
    }
    if(mom[0]<sol[0])
        return 1;
    return 0;

}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin.getline(s,N+5);
    n=strlen(s);
    for(int i=0;i<n;i++)
        v[i+1]=s[i];
    cin>>k;
    for(int i=1;i<=k;i++)
    {
        sol[0]=n;
        for(int j=1;j<=sol[0];j++)
            sol[j]=(1<<30);
        for(int l=1;l<=5;l++)
        {
            for(int st=1;st+l-1<=n;st++)
            {///continue;
                if(viz[l][st]==1)continue;
                int dr=st+l-1;
                mom[0]=0;
                for(int j=st;j<=dr;j++)
                    mom[++mom[0]]=v[j];
                if(sch()==1)
                {
                    sol[0]=mom[0];
                    for(int i=1;i<=sol[0];i++)
                        sol[i]=mom[i];
                }
            }
        }
        for(int st=1;st+sol[0]-1<=n;st++)
        {
            int dr=st+sol[0]-1;
            bool ok=1;
            int y=1;
            for(int j=st;j<=dr;j++)
            {
                if(v[j]!=sol[y])
                {
                    ok=0;
                    break;
                }
                y++;
            }
            if(ok==1)
                viz[sol[0]][st]=1;
        }
    }
    for(int i=1;i<=sol[0];i++)
        cout<<char(sol[i]);
    cout<<"\n";
    return 0;
}
/**
**/


Measured memory_bytes: 384
// Copyright (C) 2017 __debug.

// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation; version 3

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; If not, see <http://www.gnu.org/licenses/>.


#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>

#define x first
#define y second
#define MP std::make_pair
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif

using std::pair;
using std::vector;
using std::string;

typedef long long LL;
typedef pair<int, int> Pii;

const int oo = 0x3f3f3f3f;

template<typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, true : false; }
template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, true : false; }
string procStatus()
{
    std::ifstream t("/proc/self/status");
    return string(std::istreambuf_iterator<char>(t), std::istreambuf_iterator<char>());
}
template<typename T> T read(T &x)
{
    int f = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        f = (ch == '-' ? -1 : 1);
    for (x = 0; isdigit(ch); ch = getchar())
        x = 10 * x + ch - '0';
    return x *= f;
}
template<typename T> void write(T x)
{
    if (x == 0) {
        putchar('0');
        return;
    }
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    static char s[20];
    int top = 0;
    for (; x; x /= 10)
        s[++top] = x % 10 + '0';
    while (top)
        putchar(s[top--]);
}
// EOT

const int MAXN = 1e6 + 5;
const int MOD = 1e9 + 7;

int N;

void input()
{
    read(N);
}

void solve()
{
    static LL dp[MAXN];
    LL sum = 0;

    dp[0] = dp[1] = 1;
    sum = dp[0] + dp[1];
    for (int i = 2; i <= N; ++i) {
        (dp[i] = sum - dp[i - 2]) %= MOD;
        (sum += dp[i]) %= MOD;
    }

    LL ans = (dp[N - 1] * (N - 1) + dp[N]) % MOD;
    for (int i = 0; i < N - 1; ++i) {
        (ans += dp[i] * (N - 1) % MOD * (N - 1) + dp[i] * (i + 1)) %= MOD;
    }
    (ans += MOD) %= MOD;

    printf("%lld\n", ans);
}

int main()
{
#ifdef __DEBUG
    freopen("F.in", "r", stdin);
    freopen("F.out", "w", stdout);
#endif

    input();
    solve();
}

// 肠已断，泪难收。相思重上小红楼。
//     -- 辛弃疾《鹧鸪天·晚日寒鸦一片愁》


Measured memory_bytes: 8064
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <cassert>
#include <unordered_map>

#define _(x) { cout << #x << " = " << x << " "; }

const double E = 1e-8;
const double PI = acos(-1);

using namespace std;

int main() {
    long long A, ans;
    int B, C;
    scanf("%lld%d.%d",&A, &B, &C);
    ans = A * (B * 100 + C) / 100;
    printf("%lld\n", ans);
    return 0;
}



Measured memory_bytes: 1732
def kaibun(moji):
    n = len(moji)
    for i in range(0,int(n/2)):
        if s[i]!=s[n-1-i]:
            return False
    return True

s = str(input())
n = len(s)
moji1 = int((n - 1) / 2)
moji2 = int((n + 3) / 2)
#print(s[:moji1])
#print(s[moji2-1:])
if kaibun(s) and kaibun(s[:moji1]) and kaibun(s[moji2-1:]):
    print('Yes')
else:
    print('No')

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

void add357(vector<int> &array, int n, int a, int b, int c)
{
    if (a <= n)
    {
        array.push_back(a);
    }
    if (b <= n)
        array.push_back(b);
    if (c <= n)
        array.push_back(c);
    if (a <= n / 10)
        add357(array, n, a * 10 + 3, a * 10 + 5, a * 10 + 7);
    if (b <= n / 10)
        add357(array, n, b * 10 + 3, b * 10 + 5, b * 10 + 7);
    if (c <= n / 10)
        add357(array, n, c * 10 + 3, c * 10 + 5, c * 10 + 7);
}
int main()
{
    vector<int> number;
    int n, ans(0);
    cin >> n;
    add357(number, n, 3, 5, 7);
    int tmp, a3, a5, a7;
    for (int i = 0; i < number.size(); ++i)
    {
        tmp = number[i];
        a3 = 0, a5 = 0, a7 = 0;
        while (tmp)
        {
            if (tmp % 10 == 3)
                a3++;
            else if (tmp % 10 == 5)
                a5++;
            else if (tmp % 10 == 7)
                a7++;
            tmp /= 10;
        }
        if (a3 && a5 && a7)
        {
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 512
//***********************
    //*** writer : Alan Hu **
    //***********************
    #include<iostream>
    #include<vector>
    #include<string>
    #include<set>
    #include<map>
    #include<algorithm>
    #include<queue>
    #include<list>
    #include<stack>
    #include<cstdio>
    #include<fstream>
    #include<numeric>
    #include<functional>
    #include<utility>
    #include<memory>
    #include<cstring>
    #include<cmath>
    using namespace std;
         
    #define CLEAN(a,b) memset(a,b,sizeof(a))
    #define mp make_pair
    #define pb push_back
    #define sz(a) a.size()
    #define rept(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
         
    typedef long long ll;
    typedef pair<int, int> pii;
     
    int main()
    {
    	int a,b;
    	cin>>a>>b;
    	if (a+b==15) cout<<"+";
    	else if (a*b==15) cout<<"*";
    	else cout<<"x";
        return 0;
    }

Measured memory_bytes: 256
import sys


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1


def main():
    n, m = map(int, sys.stdin.buffer.readline().split())
    U = UnionFind(n)
    for x in sys.stdin.buffer.readlines():
        a, b = map(int, x.split())
        U.union(a-1, b-1)
    ans = {}
    for i in range(n):
        ans.setdefault(U._root(i), []).append(i)
    print(len(ans) - 1)


if __name__ == "__main__":
    main()


Measured memory_bytes: 23116
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n;
int nums[10000+10];
LL sum;

int main()
{
	while(~scanf("%d", &n))
	{
		if(!n)
			break;
		sum = 0;
		for(int i = 0; i < n; i++)
		{
			int tmp;
			scanf("%d", &nums[i]);
			sum += nums[i];
		}
		sum /= n;
		int ans = 0;
		for(int i = 0; i < n; i++)
		{
			if(nums[i] <= sum)
				ans++;
		}
		printf("%d\n", ans);
	}
	return 0;
}


Measured memory_bytes: 3148
#include <stdio.h>
#include <string.h>

int main() {
	static char s[256];
	int n, i, j, yes;

	scanf("%s", s);
	n = strlen(s);
	for (i = n / 2 - 1; i >= 0; i--) {
		yes = 1;
		for (j = 0; j < i; j++)
			if (s[j] != s[i + j]) {
				yes = 0;
				break;
			}
		if (yes) {
			printf("%d\n", i * 2);
			return 0;
		}
	}
	return 0;
}


Measured memory_bytes: 128
// finish date: 2018/01/10
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <algorithm>
#include <stack>
#include <map>
#include <climits>

using namespace std;

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

bool isExist(char c, string str) {
    rep(i, str.length()) {
        if (c == str[i]) return true;
    }
    return false;
}

int fact(int n) {
    int ans = 1;
    FOR(i, 1, n + 1) {
        ans *= i;
    }
    return ans;
}

int main() {
    int A, B, C;
    cin >> A >> B >> C;
    if((A==5&&B==5)||(B==5&&C==5)||(C==5&&A==5)){
        if(A==7||B==7||C==7){
            cout <<"YES"<<endl;
            return 0;
        }
    }
    cout<<"NO"<<endl;


    return 0;
}

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

signed main(void)
{
	int n, k;
	string s;
	cin >> n >> s >> k;
	rep(i, n)
	{
		if (s[i] != s[k - 1])
			s[i] = '*';
	}
	cout << s << endl;
	return 0;
}


Measured memory_bytes: 256
// う　し　た　ぷ　に　き　あ　く　ん　笑
#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define int long long

constexpr int f(int n) {
    if (n % 2) return 3 * n + 1;
    return n / 2;
}

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

    int s;
    cin >> s;

    set<int> as;

    int ai = s;
    as.insert(ai);

    for (int i = 2;; i++) {
        ai = f(ai);

        if (as.count(ai) > 0) {
            cout << i << endl;
            return 0;
        }

        as.insert(ai);
    }
}

// aiをa1から計算
// a1からaiまでをsetに記録
// もしaiが既出ならばiを出力して終了


Measured memory_bytes: 3620