akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define int long long int
using namespace std;
const int N=200001;
bool vis[N];
vector<int> adj[N];
int cyclr(int x)
{
    while(!vis[x])
    {
        vis[x]=1;
        x = adj[x][0];
    }
    return x;
}
int sizlo(int x)
{
    int s=x;
    int c=0;
    do
    {
        x = adj[x][0];
        c++;
    }
    while(x!=s);

    return c;
}
int dfs(int x, int k,int cyc)
{
   while(x!=cyc && k>0)
   {
       x = adj[x][0];
       k--;
   }
   if(x!=cyc)
   return x;

    k = k%sizlo(cyc);
    while(k>0)
   {
       x = adj[x][0];
       k--;
   }
    return x;
}
signed main() {
    ios_base::sync_with_stdio(1);
    cin.tie(0);
    cout.tie(0);
    int n,k,t;
    cin>>n>>k;
    //vector<int> arr(n+1);

    //vector<int> adj[n+1];
    for(int i=0;i<n;i++)
    {
        cin>>t;
        adj[i+1].push_back(t);
    }
    int cyc = cyclr(1);
    cout<<dfs(1,k,cyc);

    return 0;
}

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

using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)

int main()
{
    //ソートして前の数字乗
    lint mod = 998244353;
    lint n;cin >> n;
    vector<lint> d(n);
    REP(i, n) { cin >> d[i]; }
    if (d[0]!= 0)
    {
        cout << 0 << "\n";
        return 0;
    }
    sort(ALL(d));
    if(d[1]==0){
        cout << 0 << "\n";
        return 0;
    }
    if (n == 1)
    {
        cout << 1 << "\n";
        return 0;
    }
    lint num = 0;
    lint pre = 0, count = 0;
    lint c = 0,precount=1;
    lint ans = 1;
    FOR(i,1, n)
    {
        if (pre == d[i])
        {
            count++;
        }
        else
        {
            if(pre+1!=d[i]){

                cout << 0 << "\n";

                return 0;
            }
            count++;
            REP(_,count){
                ans *= precount;
                ans %= mod;
            }
            //ans*=pow(precount, count);
            precount = count;
            count = 0;
        }
        pre = d[i];
    }
    REP(_, count+1)
    {
        ans *= precount;
        ans %= mod;
    }

    cout << ans%mod <<"\n";

    return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>

using std::cin;
using std::cout;
using std::endl;

int main(void) {
  int num = 0;
  int N;
  int D;

  cin >> D >> N;

  // num = N * pow(100, D);
  int m  = pow(100, D);

  for (int i = 1; i <= N; ++i) {
    if (i % 100 == 0) num += 2 * m;
    else num += m;
  }

  cout << num << endl;
  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n,x,m,a;
    deque<int> deq;
    cin>>n;
    for (int i=0;i<n;i++) {
        cin>>x;
        deq.emplace_back(x);
    }
    cin>>m;
    for (int j=0;j<m;j++) {
        cin>>a;
        if (deq[a-1]==2019) {
            continue;
        } else if (find(deq.begin(),deq.end(),deq[a-1]+1)!=deq.end()) {
            continue;
        } else {
            deq[a-1]++;
        }
    }
    for (int k=0;k<deq.size();k++) {
        cout<<deq[k]<<endl;
    }
}


Measured memory_bytes: 3124
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ul;
typedef signed long long ll;
ul over = 1000000007;

mt19937 mt(time(nullptr));
// uniform_int_distribution< int > rand_int(0, 10) // rand[0, 10] inclusive

int main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed;
  cout << setprecision(12);
  int n, k;
  cin >> n >> k;
  double ans=0, diff=0;
  for (int i=1; i<=n; ++i) {
    int d=1;
    while (i*d<k) d*=2;
    double ans_t = ans + diff + 1.0/d/n;
    diff = ans + diff + 1.0/d/n - ans_t;
    ans = ans_t;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<numeric>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

int main(){
    ll p=pow(10,9)+7;
    int N,M;cin>>N>>M;
    if(abs(N-M)>1){
        cout<<0<<endl;
        return 0;
    }
    else{
        ll dp[100010];
        dp[0]=1;
        for(int i=1;i<=max(N,M);i++)
            dp[i]=(dp[i-1]*(ll)i)%p;
        if(N==M){
            cout<<(2*(dp[N]*dp[M])%p)%p<<endl;
            return 0;
        }
        else{
            cout<<(dp[N]*dp[M])%p<<endl;
            return 0;
        }
    }
    return 0;
}

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

using namespace std;
using ll = long long;
#define rep(i,n) for (int i = 0; i < (int)n; i++)

int main(){
  int n;
  cin >> n;
  std::vector<int> p(n);
  rep(i,n) cin >> p.at(i);
  int ans = 0;
  int curMin = 1e9;
  rep(i,n) {
    curMin = min(curMin, p.at(i));
    if (curMin == p.at(i)) ans++;
  }
  cout << ans << endl;
  return 0;
}


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

using namespace std;
const int M =1e5 + 50;
const int inf =1e9;

#define rush() int T;cin>>T;while(T--)


int qz(int x) {
	int res = 0;
	while(x) {
		res += (x%10);
		x/=10;
	}
	return res;
}

int main() {

	int n,ans = inf;
	
	
	scanf("%d",&n);
	for(int i=1;i<n;i++) {
		int tmp = qz(i) + qz(n-i);
		ans = min(ans,tmp);
	} 
	
	cout<<ans;

}




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

int main(){
    int N,M;
    cin>>N>>M;
    
    map<int,int> Year;
    map<int,int> origin;
    vector<int> P(M);
    vector<int> Y(M);
    int i;
    
    
    for(i=0;i<M;i++){
        cin>>P[i]>>Y[i];
        Year[Y[i]]=P[i];
        origin[Y[i]]=i;
    }
    
    
    sort(Y.begin(),Y.end());
    
    for(i=0;i<M;i++)P[i]=Year[Y[i]];
    
    int up[M];
    int down[M];
    int sum[100001]={0};
    
    for(i=0;i<M;i++){
        up[origin[Y[i]]]=P[i];
        sum[P[i]]++;
        down[origin[Y[i]]]=sum[P[i]];
        
    }
    
    for(i=0;i<M;i++)printf("%06d%06d\n",up[i],down[i]);
    
}

Measured memory_bytes: 12928
#include<iostream>
using namespace std;
struct node{
	int d,l,r;
}sp[200];
int main()
{
	int arr[4][4]={0};
	for(int i=1;i<=3;++i)
	for(int j=1;j<=3;++j)
	{
		int d;
		cin>>d;
		sp[d]={1,i,j};
	}
	int cnt;
	cin>>cnt;
	for(int i=1;i<=cnt;++i)
	{
		int q;
		cin>>q;
		if(sp[q].d==1)arr[sp[q].l][sp[q].r]=1;
	}
	for(int i=1;i<=3;++i)
	{
	int sum=0,ss=0;
	for(int j=1;j<=3;++j)
	{
		sum+=arr[i][j];
		ss+=arr[j][i];
	}
	if(sum==3||ss==3){cout<<"Yes";return 0;}
	}
	if((arr[1][1]+arr[2][2]+arr[3][3])==3||(arr[1][3]+arr[2][2]+arr[3][1])==3){cout<<"Yes";return 0;}
	cout<<"No";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#include <numeric>
#define PI 3.14159265358979323846
#define MAXINF (1e18L)
#define INF (1e9L)
#define EPS (1e-9)
#define MOD (1'000'000'007)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define FIND(v,x) (binary_search(ALL(v),(x)))
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define pb push_back
#define fi first
#define se second
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
typedef long long ll;
typedef pair<int, int> pii;

int main(void)
{
    ll w,h;
    cin >> w >> h;
    ll x,y;
    cin >> x >> y;

    char s = '0';
    if(w%2==0 && w/2==x && h%2==0 && h/2==y) s = '1';

    printf("%lf %c\n",w*h/2.0, s);
}

Measured memory_bytes: 256
def main():
    N = int(input())
    A = sorted(map(int, input().split()), reverse=True)
    print(A[0] + sum(A[1:(N - 2) // 2 + 1]) * 2 + A[(N - 2) // 2 + 1] * (N % 2))


if __name__ == "__main__":
    main()


Measured memory_bytes: 31428
#include <bits/stdc++.h>
#include <string>
#include <vector>
#include <algorithm>
#define rep(i,w) for (int i = 0;i < (w); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
int INF = 1e9;

int main(){
  int n,m;cin >> n >> m;
  vector<ll> x(n),y(n),z(n);
  rep(i,n) cin >> x[i] >> y[i] >> z[i];
  vector<ll> cons(n);
  ll ans = -1e18;
  rep(plus,1<<3){
    int a,b,c;
    if(plus>>0&1) a = 1;
    else a = -1;
    if(plus>>1&1) b = 1;
    else b = -1;
    if(plus>>2&1) c = 1;
    else c = -1;
    rep(i,n) cons[i] = a*x[i] + b*y[i] + c*z[i];
    sort(cons.rbegin(),cons.rend());
    ll sum = 0;
    rep(i,m) sum += cons[i];
    ans = max(ans,sum);
  }

  cout << ans << endl;
}

Measured memory_bytes: 3676
#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <utility>
#include <complex>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <tuple>
#include <bitset>
#include <limits>
#include <algorithm>
#include <array>
#include <random>
#include <complex>
#include <regex>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef complex<ld> compd;
#define quickIO()	{cin.tie(0);	cout.sync_with_stdio(false);}
#define reach(i,a)	for(auto i:a)
#define rep(i,n)	for(int i=0;i<((int)n);i++)
#define REP(i,n)	for(int i=0;i<=((int)n);i++)
#define srep(i,a,n)	for(int i=a;i<((int)n);i++)
#define SREP(i,a,n)	for(int i=a;i<=((int)n);i++)
#define rrep(i,n)	for(int i=n-1;i>=0;i--)
#define RREP(i,n)	for(int i=n;i>=0;i--)
#define all(a)	(a).begin(),(a).end()
#define mp(a,b)	make_pair(a,b)
#define mt	make_tuple
#define pb	push_back
int bitcnt(ll x) {
	x = ((x & 0xAAAAAAAAAAAAAAAA) >> 1) + (x & 0x5555555555555555);
	x = ((x & 0xCCCCCCCCCCCCCCCC) >> 2) + (x & 0x3333333333333333);
	x = ((x & 0xF0F0F0F0F0F0F0F0) >> 4) + (x & 0x0F0F0F0F0F0F0F0F);
	x = ((x & 0xFF00FF00FF00FF00) >> 8) + (x & 0x00FF00FF00FF00FF);
	x = ((x & 0xFFFF0000FFFF0000) >> 16) + (x & 0x0000FFFF0000FFFF);
	x = ((x & 0xFFFFFFFF00000000) >> 32) + (x & 0x00000000FFFFFFFF);
	return x;
}
int bitcnt(int x) {
	x = ((x & 0xAAAAAAAA) >> 1) + (x & 0x55555555);
	x = ((x & 0xCCCCCCCC) >> 2) + (x & 0x33333333);
	x = ((x & 0xF0F0F0F0) >> 4) + (x & 0x0F0F0F0F);
	x = ((x & 0xFF00FF00) >> 8) + (x & 0x00FF00FF);
	x = ((x & 0xFFFF0000) >> 16) + (x & 0x0000FFFF);
	return x;
}
ll sqrtll(ll x) {
	ll left = 0, right = x;
	rep(i, 100) {
		ll mid = (left + right) >> 1;
		if (mid*mid <= x)	left = mid;
		else	right = mid;
	}
	return left;
}
ll gcd(ll a, ll b) {
	return a % b == 0 ? b : gcd(b, a%b);
}
#define debug(x)	printf("Case #%d: ", x)
#define DEBUG 0
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ld eps = 1e-9;
const int dx[] = { 1,0,-1,0,0 };
const int dy[] = { 0,1,0,-1,0 };

int main() {
	int n, c;	cin >> n >> c;
	vector<vint> d(c, vint(c));
	rep(i, c)	rep(j, c)	cin >> d[i][j];
	vector<vint> g(n, vint(n));
	rep(i, n)	rep(j, n)	cin >> g[i][j];
	// mod=0,1,2でまとめてしまう
	// mod=0,1,2のマスを色iに変えるために必要なコスト
	vector<vint> change(3, vint(c, 0));
	rep(i, 3) {
		rep(j, c) {
			rep(a, n)	rep(b, n) {
				if ((a + b) % 3 == i)	change[i][j] += d[g[a][b] - 1][j];
			}
		}
	}
	// 後は全探索しましょう
	int ret = mod;
	rep(i, c)	rep(j, c)	rep(k, c) {
		if (i == j || i == k || j == k)	continue;
		int tmp = change[0][i] + change[1][j] + change[2][k];
		ret = min(ret, tmp);
	}
	cout << ret << endl;
	return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--) 
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define downque(que) priority_queue<ll> que;
#define upque(que) priority_queue<ll, vector<int>, greater<int>> que;
typedef long long ll;
typedef vector<vector<int>> Matrix;
const int MOD = 1e9 + 7;
const int MAX = 1e7;
const int INF = numeric_limits<int>::max();

int main(){
 int n,m,x,sum=0,res=0; cin>>n>>m;
 vector<int> a(n);
 REP(i,n){
     cin>>a[i];
     sum+=a[i];
 }
sort(ALL(a));
reverse(ALL(a));
x=sum/(4*m);
if(sum%(4*m)>0)x++;
if(a[m-1]>=x)
  cout << "Yes" << endl;
  else
    cout << "No" << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    string s;
    while(getline(cin,s),s!="."){
        stack<int> b;
        bool isBn=true;
        for(auto c : s){
            if(c=='(') b.push(1);
            if(c=='[') b.push(2);
            if(c==')'){
                if(!b.empty() && b.top()==1){
                    b.pop();
                }else{
                    isBn=false;
                    break;
                }
            }
            if(c==']'){
                if(!b.empty() && b.top()==2){
                    b.pop();
                }else{
                    isBn=false;
                    break;
                }
            }
        }
        if(isBn==false || !b.empty()){
            cout<<"no"<<endl;
        }else{
            cout<<"yes"<<endl;
        }
    }
}

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

bool ss(int x){
	int i;
	i=2;
 if(x==1||x==0) return false;
	while(i*i <= x && x % i != 0) i++;
   return  i*i >x ;
}
int main(){
	int ans = 0,i,a;
	int n;
	cin>>n;
	for(int i = 0;i < n;i++)
	{
		cin>>a;
		ans += ss(a);
	}
	
	cout<<ans<<endl;
	
	return 0;
} 



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

using namespace std;
using LL = long long;
using P = pair<int,int>;
const LL INF=1e15;

int main(){
	LL N;
	cin >> N;
	vector<LL> A(N+1);
	rep(i,N+1) cin >> A[i];
	vector<LL> max_down(N+1);
	max_down[0]=1;
	for(LL i=1; i<=N; i++){
		LL num=max_down[i-1]-A[i-1];
		if(num<=0){
			cout << -1 << endl;
			return 0;
		}
		if(num>INF){
			max_down[i]=INF;
			continue;
		}
		LL m=0;
		if(i>=50) m=num*2;
		else{
			LL M=pow(2,i);
			m=min(num*2,M);
		}
		max_down[i]=m;
	}
	if(max_down[N]<A[N]){
		cout << -1 << endl;
		return 0;
	}
	LL ans=A[N], max_prev=A[N];
	for(LL i=N-1; i>=0; i--){
		LL m=max_prev+A[i];
		max_prev=min(m,max_down[i]);
		ans+=max_prev;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 5084
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <functional>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
using llong = long long;

const llong mod = (llong)(1e9) + 7;
string l;
llong dp[2][2][2][100005];

llong dfs(int smaller, int n, int m, int i) {
    if (dp[smaller][n][m][i] != -1) return dp[smaller][n][m][i];
    if (l.size() == i) return 1;

    if (l[i + 1] == '0' && smaller == 0) {
        return dp[smaller][n][m][i] = dfs(smaller, 0, 0, i + 1) % mod;
    }
    else {
        return dp[smaller][n][m][i] = (dfs(smaller, 0, 1, i + 1) + dfs(smaller, 1, 0, i + 1) +
                                       dfs(1, 0, 0, i + 1)) % mod;
    }
}

llong pow_mod(llong n, llong m) {
    llong res = 1;

    while (m) {
        if (m & 1) {
            res *= n;
            res %= mod;
        }

        n *= n;
        n %= mod;
        m >>= 1;
    }

    return res;
}

int main() {
    cin >> l;

    for (int i = 0; i < 100005; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                dp[j][k][0][i] = -1;
                dp[j][k][1][i] = -1;
            }
        }
    }

    dfs(1, 0, 0, 0);
    dfs(0, 0, 1, 0);
    dfs(0, 1, 0, 0);

    cout << (dp[1][0][0][0] + dp[0][0][1][0] + dp[0][1][0][0]) * pow_mod(3, mod - 2) % mod << endl;

    return 0;
}


Measured memory_bytes: 12928
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

int main()
{
  i64 n;
  cin >> n;
  vector<i64> p(n);
  for (i64 i = 0; i < n; i++)
    cin >> p[i];
  i64 ans = 0, m = 1e9;
  for (i64 i = 0; i < n; i++)
  {
    if (p[i] <= m)
      ans++;
    m = min(m, p[i]);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  long long time=0;
  bool flag = true;
  cin >> n;
  vector<pair<long long , long long>> pair(n);
  for(int i=0; i<n; i++){
    cin >> pair.at(i).second >> pair.at(i).first;
  }
  
  sort(pair.begin(),pair.end());
  
  for(int i=0; i<n; i++){
    time += pair.at(i).second;
    if(time > pair.at(i).first){
      flag = false;
      break;
    }
  }
  
  if(flag){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

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

int main() {
	ll n, m;
	cin >> n >> m;
	ll count = 0;
	if (n >= 2 && m >= 2) {
		count += (n - 2)*(m - 2);
	}
	else if (n == 1) {
		if (m == 1) {
			count++;
		}
		else {
			count += m - 2;
		}
	}
	else {
		count += n - 2;
	}
	cout << count;
	return 0;
}

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

int main() {
  int64_t L, R, tmp, mi = 2020;
  cin >> L >> R;
  
  for(int64_t i=L; i<=R-1; i++){
    for(int64_t j=i+1; j<=R; j++){
      tmp = ((i%2019)*(j%2019))%2019;
      if(tmp < mi) mi = tmp;
      if(mi == 0) break;
    }
    if(mi == 0) break;
  }
  cout << mi << endl;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))
b = []

ind1 = 0

for i in a:
    if i == 1:
        break
    ind1 += 1


if 1 in a:
    b.append(1)
    for i in range(ind1, len(a)):
        if a[i] == b[-1] + 1:
            b.append(a[i])

if len(b) == 0:
    print(-1)
else:
    print(n - len(b))


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

int main() {	
    int A, B; cin >> A; cin >> B;
  
    int SumA = A + B;
    int SumB = A - B;
    int SumC = A * B;

  	cout << max({SumA, SumB, SumC}) << endl;
  
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define s second
#define f first
#define pb push_back
#define endl '\n'
using namespace std;


typedef long long ll;
typedef pair<int,int> pii;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;

string S;
ll ans = 0;

ll go(string t){

	t += '+';
	string aux = "";

	ll ret = 0;

	for(int i = 0; i < (int)t.size(); i++){
		if(t[i] == '+'){
			ret += stoll(aux);
			aux = "";
		}
		else{
			aux += t[i];
		}
	}
	
	return ret;
}

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

	cin >> S;

	int N = S.size() - 1;

	for(int mask = 0; mask < (1ll<<N); mask++){
		
		string aux = "";
		aux += S[0];

		for(int i = 0; i < N; i++){
			if(mask >> i & 1){
				aux += '+';
			}
			aux += S[i+1];
		}

		ans += go(aux);
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3604
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<map>
using namespace std;
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 long long INF = 1LL << 60;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main(){
    int n;
    cin>>n;
    map<string,int> memo;
    rep(i,n){
        string s;
        cin>>s;
        if(memo[s]!=1){
            memo[s]++;
        }
    }
    int Sum=0;
    for(auto itr=memo.begin();itr!=memo.end();itr++){
        Sum+=itr->second;
    }
    cout<<Sum<<endl;
}


Measured memory_bytes: 19236
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define FORR(i,a,b) for (int i=(a);i>=(b);i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define show(x) cout<<#x<<" = "<<x<<endl;
#define rng(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef set<int> si;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pll> vpll;
typedef set<ll> sl;
typedef __int128_t lll;
typedef pair<lll,lll> plll;
typedef vector<lll> vlll;
template<typename T>string join(vector<T>&v){stringstream s;FOR(i,0,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename A,size_t N,typename T>void Fill(A (&array)[N],const T&v){fill((T*)array,(T*)(array+N),v);}
lll gcd(lll a,lll b,lll &x,lll &y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll gcd(ll a,ll b){lll x=0,y=0;return gcd(a,b,x,y);}
ll modpow(lll a,lll n,ll m){if(a==0)return a;lll p=1;for(;n>0;n<<=1,a=a*a%m)if(n&1)p=p*a%m;return(ll)p;}
void dout(double d){printf("%.12f\n",d);}
void YN(bool z){cout<<(z?"YES\n":"NO\n");}
void Yn(bool z){cout<<(z?"Yes\n":"No\n");}
void yn(bool z){cout<<(z?"yes\n":"no\n");}

const int iinf = 1e9;
const ll linf = 1e18;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-10;
const int N = 0;
struct Prime{
  vector<ll> pl;
  void init(int a){ // a以下の素数列挙
    pl.resize(0);
    vector<bool> z(a+1, true);
    FOR(i, 2, a+1){
      if(z[i])pl.push_back(i);
      for(int b=i*2; b <= a; b+=i) z[b]=false;
    }
  }
  void divisor(ll a, vector<ll>&v){ // v に約数が入る
    v.resize(0);
    v.push_back(1);
    for(ll b: pl){
      if(b*b > a) break;
      if(a%b) continue;
      int l=0, vs=v.size();
      while(a%b==0){
        a /= b;
        FORR(i, v.size()-1, l) v.push_back(v[i] * b);
        l += vs;
      }
    }
    if(a>1) FORR(i, v.size()-1, 0) v.push_back(v[i] * a);
    sort(v.begin(), v.end());
  }
} pr;
ll n, m;
vl v;

main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> m;
  pr.init(32000);
  pr.divisor(m, v);
  for(ll a: v)if(a >= n){
    cout << m/a << endl;
    return 0;
  }
}

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

using namespace std;
typedef long long ll;

#define rep(i, N) for(ll i=0; i<(N); ++i)

//sqrtN -> 最大値のみに対応できればいいので，それを使う
const int sqrtN = 512;
struct SqrtDecomposition {
  int N, K;
  vector<int> data;
  vector<int> bucketSum;
  SqrtDecomposition(int n) : N(n) {
    K = (N + sqrtN - 1) / sqrtN;
    data.assign(K * sqrtN, 0);
    bucketSum.assign(K, 0);
  }
  void add(int x, int y) {
    int k = x / sqrtN;
    data[x] += y;
    int sum = 0;
    for(int i = k * sqrtN; i < (k + 1) * sqrtN; ++i) {
      sum += data[i];
    }
    bucketSum[k] = sum;
  }
  // [x, y)
  int getSum(int x, int y) {
    int sum = 0;
    for (int k = 0; k < K; ++k) {
      int l = k * sqrtN, r = (k + 1) * sqrtN;
      if (r <= x || y <= l)
        continue;
      if (x <= l && r <= y) {
        sum += bucketSum[k];
      } else {
        for (int i = max(x, l); i < min(y, r); ++i) {
          sum += data[i];
        }
      }
    }
    return sum;
  }
};

int main() {
  //range sum query
  int n, q;
  cin >> n >> q;
  
  SqrtDecomposition dec(n);
  vector<string> res;
  rep(_, q) {
    int c, x, y;
    cin >> c >> x >> y;
    if(c == 0) {
      dec.add(x, y);
    } else {
      cout << dec.getSum(x, y + 1) << endl;
    }
  }
}



Measured memory_bytes: 3136
import java.util.*;
public class Main{
    public static void main(String[] args){
	new Main().run();
    }
    Scanner sc = new Scanner(System.in);

    Player[] p;
    int n;

    void run(){
	while(sc.hasNext()){
	    n = sc.nextInt();
	    p = new Player[n];
	    for(int i=0; i<n; i++)
		p[i] = new Player(sc.nextInt(), sc.nextInt());
	    
	    
	    Arrays.sort(p, new Comparator<Player>(){
		    public int compare(Player p1, Player p2){
			int g1 = p1.getGet();
			int g2 = p2.getGet();
			if(g1 != g2) return g2-g1;
			int n1 = p1.getNum();
			int n2 = p2.getNum();
			return n1-n2;
		    }
		}
		);

	    System.out.println(p[0].getNum()+" "+p[0].getGet());
	}
    }

    class Player{
	int num, get;
	Player(int n, int g){
	    num = n;
	    get = g;
	}
	int getGet(){ return get; }
	int getNum(){ return num; }
    }
}

Measured memory_bytes: 17272
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define F first
#define S second
#define mkp make_pair
#define pii pair<int,int>
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=1e5+5;

int main(){
	int a,b;
	cin>>a>>b;
	for(int i=1;i<=10000;i++){
		if(int(i*0.08)==a&&int(i*0.1)==b){
			cout<<i;
			return 0;
		}	
	}
	cout<<-1;
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
    int k,s,a,b,c,cnt=0;
    scanf("%d %d", &k, &s);
    for(a=0; a<=k; a++){
        for(b=0; b<=k; b++){
            c=s-a-b;
            if(c<=k && c>=0)
              cnt+=1;
        }
    }
    printf("%d",cnt);
    return 0;
}

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

int main()
{
	int n;
	cin >> n;
	vector<int> a(n);
	for(int i = 0;i<n;i++)
	{
		cin >> a[i];
	}
	vector<int> v;
	for(int i = 0;i<n;i++)
	{
		auto x = upper_bound(v.begin(),v.end(),a[i],greater<>());
		if(x==v.end())
		{
			v.push_back(a[i]);
		}
		else
		{
			*x = a[i];
		}
		
	}
	cout<<v.size()<<endl;
	return 0;
}

Measured memory_bytes: 1404
#include <cstdio>

#define N (200000 + 5)
#define mod 1000000007

struct edge{
    int to, nxt;
}e[2 * N];

typedef long long ll;
ll frac[N], inv[N], dp[N], pa[N], ans[N];
int fir[N], size[N], tot, n;

void addedge(int u, int v)
{
    e[++tot].to = v;
    e[tot].nxt = fir[u];
    fir[u] = tot;
}

ll pow(ll x, int k)
{
    if(k == 1) return x;
    ll ret = pow(x, k>>1);
    if(k&1) return ret * ret % mod * x % mod;
    return ret * ret % mod;
}

void dfs1(int x, int p)
{
    dp[x] = size[x] = 1;
    for(int i = fir[x]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == p) continue;
        dfs1(v, x);
        size[x] += size[v];
        dp[x] *= dp[v], dp[x] %= mod;
        dp[x] *= inv[size[v]], dp[x] %= mod;
    }
    dp[x] *= frac[size[x] - 1], dp[x] %= mod;
}

void dfs2(int x, int p)
{
    ans[x] = dp[x] * frac[n - 1] % mod * inv[size[x] - 1] % mod * pa[x] % mod * inv[n - size[x]] % mod;
    for(int i = fir[x]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == p) continue;
        pa[v] = dp[x] * frac[size[v]] % mod * inv[n - size[x]] % mod * inv[size[x] - 1] % mod 
                * frac[n - size[v] - 1] % mod * pow(dp[v], mod - 2) % mod * pa[x] % mod;
        dfs2(v, x);
    }
}

int main()
{
    //freopen("a.in", "r", stdin);
    scanf("%d", &n);
    for(int i = 1; i < n; i++)
    {
        int x, y; scanf("%d%d", &x, &y);
        addedge(x, y);
        addedge(y, x);
    }
    frac[0] = 1;
    for(int i = 1; i <= n; i++)
        frac[i] = frac[i - 1] * i % mod, inv[i] = pow(frac[i], mod - 2);
    dfs1(1, 0);
    pa[1] = inv[0] = 1;
    dfs2(1, 0);
    for(int i = 1; i <= n; i++)
        printf("%lld\n", ans[i]);
    return 0;
}

Measured memory_bytes: 14720
#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using i64 = int64_t;
constexpr i64 INF = 1'010'000'000'000'000'017LL;
#define _overload3(_1,_2,_3,name,...) name
#define repi(i,start,end) for(int i=(start);i<(end);++i)
#define _rep(i,n) repi(i,0,n)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(i,start,end) for(int i=(start);i>end;--i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define v(T) vector<T>
#define vv(T) v(v(T))
#define vvv(T) v(v(v(T)))
typedef pair<int,int> P;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream &operator<<(ostream &os, const vector< T > &v){
  rep(i,v.size()) os << v[i] << (i + 1 != v.size() ? " " : "");
  return os;
}
template<typename T> istream &operator>>(istream &is, vector< T > &v){
  for(T &in : v) is >> in;
  return is;
}

void Main()
{
  int A, B, Q;
  cin >> A >> B >> Q;
  v(i64) S(A), T(B), X(Q);
  cin >> S >> T >> X;

  S.emplace_back(INF);
  S.emplace_back(-1 * INF);
  T.emplace_back(INF);
  T.emplace_back(-1 * INF);

  sort(rng(S));
  sort(rng(T));

  int s, t;
  i64 sl, sr, tl, tr;
  for(auto &x:X){
    i64 ans = INF;

    s = lower_bound(rng(S), x) - S.begin();
    t = lower_bound(rng(T), x) - T.begin();
    sr = S[s] - x;
    sl = x - S[s-1];
    tr = T[t] - x;
    tl = x - T[t-1];

    chmin(ans, max(sl, tl));
    chmin(ans, max(sr, tr));
    chmin(ans, sl * 2 + tr);
    chmin(ans, tl * 2 + sr);
    chmin(ans, sr * 2 + tl);
    chmin(ans, tr * 2 + sl);
    cout << ans << "\n";
  }
}

int main()
{
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  Main();
}

Measured memory_bytes: 3680
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int []u = new int[N - 1];
		int []v = new int[N - 1];
		long []cost = new long[N - 1];
		for (int i = 0; i < N - 1; i++) {
		    u[i] = sc.nextInt() - 1;
		    v[i] = sc.nextInt() - 1;
		    cost[i] = sc.nextInt();
		}
		long []d = dijkstra(N, 0, u, v, cost, true);
		int []id = new int[N];
		id[0] = 0;
		for (int i = 1; i < N; i++) {
		    if (d[i] % 2 == 0) {
		        id[i] = 0;
		    } else {
		        id[i] = 1;
		    }
		}
		for (int i : id) {
		    System.out.println(i);
		}
	}
	/**
	 * ダイクストラ法 (優先度付きキュー)
	 * @param N 頂点数 (0 ~ N-1)
	 * @param t 始点
	 * @param from, to 辺
	 * @param cost 辺のコスト
	 * @param flag true なら無向辺、 false なら有向辺
	 * @return d t から各頂点への最短距離
	 */
	public static long[] dijkstra(int N, int t, int[] from, int[] to, long[] cost, boolean flag) {
		final int WHITE = 0;
	    final int GRAY = 1;
	    final int BLACK = 2;
	    final long INF = 100000000000000l;
		long[] d = new long[N];
		int[] color = new int[N];
		@SuppressWarnings("unchecked")
		ArrayList<Node>[] adj = new ArrayList[N];
		for(int i = 0; i < N; i++) {
			d[i] = INF;
			color[i] = WHITE;
			adj[i] = new ArrayList<Node>();
		}
		int E = from.length;
		for(int i = 0; i < E; i++) {
			adj[from[i]].add(new Node(to[i], cost[i]));
			if(flag)adj[to[i]].add(new Node(from[i], cost[i]));
 
		}
		Queue<Node> pq = new PriorityQueue<Node>(new MyComparator());
		d[t] = 0;
		pq.add(new Node(t, 0l));
		while(!pq.isEmpty()) {
			Node f = pq.poll();
			int u = f.id;
			color[u] = BLACK;
			if(d[u] < f.cost) continue;
			for(int j = 0; j < adj[u].size(); j++) {
				int v = adj[u].get(j).id;
				if(color[v] == BLACK) continue;
				if(d[v] > d[u] + adj[u].get(j).cost) {
					d[v] = d[u] + adj[u].get(j).cost;
					pq.add(new Node(v, d[v]));
					color[v] = GRAY;
				}
			}
		}
		return d;
	}
	static class Node{
		int id;
		long cost;
		public Node(int id, long cost) {
			this.id = id;
			this.cost = cost;
		}
	}
	static class MyComparator implements Comparator<Node>{
		@Override
        public int compare(Node v1, Node v2) {
			if(v1.cost < v2.cost) {
				return -1;
			}else if(v1.cost == v2.cost) {
				return 0;
			}else {
				return 1;
			}
		}
	}
}


Measured memory_bytes: 104984
#include<bits/stdc++.h>
using namespace std;
#define f_input(i,a,dd) for(i=0; i<a; i++)cin>>dd[i];
#define sort(a) sort(a.begin(),a.end(),greater<int>());
int main()
{
    int x,y,a,b,c,i,j;
    cin>>x>>y>>a>>b>>c;
    vector<int>red(a),green(b),clrls(c);
    f_input(i,a,red);
    f_input(i,b,green);
    f_input(i,c,clrls);
    sort(red);
    sort(green);
    sort(clrls);
    long long int total=0;
    priority_queue<int>pq;
    for(i=0; i<x; i++)
        pq.push(red[i]);
    for(i=0; i<y; i++)
        pq.push(green[i]);
    for(i=0; i<c; i++)
        pq.push(clrls[i]);
    for(i=0; i<x+y; i++)
    {
        total+=pq.top();
        pq.pop();
    }
    cout<<total<<endl;
}




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

using namespace std;

typedef long long ll;

int main() {
 int n;
 cin>>n;
 vector<pair<ll,ll>> ps(n),ps2(n);
 for (int i = 0; i < n; i++) {
   cin>>ps[i].first>>ps[i].second;
 }
 sort(ps.begin(),ps.end());
 ps2[0].first = ps2[0].second = 0;
 map<string, int> mp;
 for (int i = 1; i < n; i++) {
   for (int j = 0; j < i; j++) {
        ll a = ps[i].first - ps[j].first;
        ll b = ps[i].second - ps[j].second;
        string s = to_string(a) + " " + to_string(b);
        mp[s]++;
   }
 }
 int maxv = 0;
 for (auto p : mp) {
   int tmp = p.second;
   maxv = max(maxv,tmp);
 }
 int ans = n - maxv;
 cout<<ans<<endl;
return 0;
}

Measured memory_bytes: 384
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
int main() {
	int N;
	cin >> N;
	vector<int> a;
	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;
		a.push_back(x);
	}
	sort(a.rbegin(), a.rend());
	int sumA = 0, sumB = 0;
	for (int i = 0; i < a.size(); i++) {
		if (i % 2 == 0) sumA += a[i];
		else sumB += a[i];
	}
	cout << sumA - sumB << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
void solve(void){
  int D, N;
  cin >> D >> N;
  if(N==100) N++;
  cout << N;
  for(int i=0; i<2*D; ++i){
    cout << "0";
  }
  cout << endl;
}
 
int main(void){
  solve();
  return 0;
}

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

int main(void){

	int k; cin >> k;
	int ki, gu;
	if (k % 2 == 0){
		ki = k / 2;
		gu = k / 2;
	}
	if (k % 2 == 1){
		ki = k / 2 + 1;
		gu = k / 2;
	}

	cout << ki * gu << endl;

	return 0;
}

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

int main() {
    int n;
    cin >> n;
    int A[n];
    for(int i = 0; i < n; i++){
        cin >> A[i];
    }
    sort(A,A+n);
    cout << A[n-1] - A[0] << endl;
    return 0;
}




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

int main()
{
    int N, R = 0;
    cin >> N >> R;
    if (N >= 10)
    {
        cout << R << endl;
    }
    else{
        cout << 100 *(10 -N)+R << endl;
    }
}

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

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define _USE_MATH_DEFINES
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define INF 1000000000000000
#define MAXN (int)(1e5)+1
#define MOD 1000000007

using namespace std;

typedef long long int lli;
typedef pair<int,int> pii;
typedef pair<lli,int> pwi;
typedef pair<lli,lli> plli;
typedef vector<int> vi;
typedef vector<lli> vlli;
typedef vector< vector<pair<int,lli > > > wGraph;
//typedef vector<vector<int> > graph;
typedef vector<vector<lli> > matrix;

lli som(lli a,lli b){
	return ((a%MOD)+(b%MOD))%MOD;
}

char mat[1001][1001];

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout<<std::fixed;
    cout<<std::setprecision(7);

    int h,w;
    cin>>h>>w;

    for(int i = 1;i<=h;++i){
    	for(int j = 1;j<=w;++j){
    		cin>>mat[i][j];
    	}
    }

    lli dp[h+1][w+1];
    for(int i = 1;i<=h;++i){
    	for(int j = 1;j<=w;++j){

    		if(mat[i][j] == '#'){
    			dp[i][j] = 0;
    			continue;
    		}
    		if(i == 1 && j == 1){
    			dp[i][j] = 1;
    		}else if(i-1>0 && j-1>0){
    			dp[i][j] = som(dp[i-1][j],dp[i][j-1]);
    		}else if(i-1>0){
    			dp[i][j] = dp[i-1][j];
    		}else{
    			dp[i][j] = dp[i][j-1];
    		}

    	}
    }

    cout<<dp[h][w]<<endl;

    return 0;

}


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

int main() {
	ll N;
	set<ll> s;
	cin >> N;

	for(ll i=1; i*i<=N-1; ++i)
		if((N-1)%i == 0) {
			s.insert(i);
			s.insert((N-1)/i);
		}

	for(ll i=1; i*i<=N; ++i) {
		if(N%i != 0)
			continue;

		ll t=N;
		if(i != 1) {
			while(t%i == 0)
				t /= i;
			if(t%i == 1)
				s.insert(i);
		}

		t=N;
		while(t%(N/i) == 0)
			t /= (N/i);
		if(t%(N/i) == 1)
			s.insert(N/i);
	}

	cout << s.size()-1 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for (ll i=0; i<n; ++i)
#define all(c) begin(c),end(c)
#define PI acos(-1)
#define oo LLONG_MAX
template<typename T1, typename T2>
bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;}
template<typename T1, typename T2>
bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;}
/*

*/
int main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  
  ll N, X, T, ans = 0;
  cin >> N >> X >> T;

  ans = N/X;
  if (N%X)
    ans++;
  ans *= T;
  cout << ans << endl;
  
}


Measured memory_bytes: 3608
#include<iostream>
using namespace std;
int main()
{
    char a,b;
    cin>>a;
    if(a=='A')b='T';
    if(a=='G')b='C';
    if(a=='C')b='G';
    if(a=='T')b='A';
    cout<<b<<endl;
    return 0;
}

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

#define rep(i,j,n) for(int i=j;i<n;++i)
#define all(i) i.begin(),i.end()
#define rall(i) i.rbegin(), i.rend()
#define INF 1e9
#define LINF 1e18
const int mod = 1e9 + 7;

typedef long long i64;
typedef pair<int, int> pi;

template <class T> using vt = vector<T>;
template <class T> using vvt = vector<vector<T>>;

i64 gcd(i64 n, i64 m) {return (m == 0? n : gcd(m, n % m));}
i64 lcd(i64 n, i64 m) {return (n / gcd(n, m) * m);}
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

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

  int n;
  cin >> n;
  vt<int> c(n);
  rep(i, 0, n) cin >> c[i];

  c.erase(unique(all(c)), c.end());
  n = c.size();

  vt<int> dp(n), sum(200100);
  dp[0] = sum[c[0]] = 1;
  rep(i, 0, n - 1) {
    dp[i + 1] = dp[i] + sum[c[i + 1]];
    dp[i + 1] %= mod;
    sum[c[i + 1]] = dp[i + 1];
  }
  cout << dp[n - 1] << endl;
}

Measured memory_bytes: 2688
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
#include <map>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <bitset>
#define f first
#define s second
#define ll long long
#define ull unsigned long long
#define mp make_pair
#define pb push_back
#define vi vector <int>
#define ld long double
#define pii pair<int, int>
#define y1 sda
using namespace std;    
const int N = int(4e5) + 10, mod = int(1e9)  + 7; 

int n;
int a[N];
ll ans;

int main () {
	scanf("%d",&n);
	for(int i = 1; i <= 3 * n; i++){
		scanf("%d",&a[i]);
	}
	sort(a + 1, a + 3 * n + 1);
	for(int i = 3 * n - 1, j = n; i > 0 && j > 0; i -= 2, j--){
		ans += a[i];
	}
	printf("%lld", ans);


return 0;
}

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

#define int             long long
#define FOR( i, m, n )  for( int (i) = (m); (i) < (n); (i)++ )
#define REP( i, n )     FOR( i, 0, n )
#define REPR( i, m )    for( int (i) = (m); (i) >= 0; (i)-- )
#define REPONE( i, n )  FOR( i, 1, n + 1 )
#define ALL( a )        (a).begin(), (a).end()
#define MP              make_pair

using namespace std;
using P = pair<int, int>;
using PP = pair<int, pair<int, int> >;

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

const int INF = 1e9;
const int INFLL = 1e18;
const int MOD = 1e9 + 7;

int dp[110][10001];

signed main(){
    int N, W; cin >> N >> W;
    vector<int> v( N ), w( N );
    REP( i, N ) cin >> v[i] >> w[i];

    REP( i, N ){
        REP( j, W + 1 ){
            if( w[i] <= j ){
                dp[i + 1][j] = max( dp[i][j], dp[i + 1][j - w[i]] + v[i] );
            }else{
                dp[i + 1][j] = dp[i][j];
            }
        }
    }

    cout << dp[N][W] << endl;
}



Measured memory_bytes: 10908
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)
 
int main() {
    int n, k;
    cin >> n >> k;
    int ans = 0;
    while(n){
        ans++;
        n /= k;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(){
    int n;
while(scanf("%d",&n)==1){

if(n==0)printf("1\n");
if(n==1)printf("1\n");
if(n==2)printf("2\n");
if(n==3)printf("6\n");
if(n==4)printf("24\n");
if(n==5)printf("120\n");
if(n==6)printf("720\n");
if(n==7)printf("5040\n");
if(n==8)printf("40320\n");
if(n==9)printf("362880\n");
if(n==10)printf("3628800\n");
if(n==11)printf("39916800\n");
if(n==12)printf("479001600\n");
if(n==13)printf("6227020800\n");
if(n==14)printf("87178291200\n");
if(n==15)printf("1307674368000\n");
if(n==16)printf("20922789888000\n");
if(n==17)printf("355687428096000\n");
if(n==19)printf("121645100408832000\n");
if(n==20)printf("2432902008176640000\n");


            }

return 0;


}

Measured memory_bytes: 1004
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define dbg(x) cerr << #x << " = " << x << endl
#define _ << ' ' <<
using namespace std;
using ll = long long;
using vi = vector<int>;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a[3];
    for (int i = 0; i < 3; ++i)
        cin >> a[i];
    sort(a, a + 3);
    cout << a[0] * a[1]  / 2;
}


Measured memory_bytes: 256
def main():
    goods, weight_limit = map(int, input().split())
    weight = []
    value = []
    for _ in range(goods):
        w, v = map(int, input().split())
        weight.append(w)
        value.append(v)
    max_value = 10 ** 5 + 10
    dp = [[float("inf") for _ in range(max_value + 1)] for _ in range(goods + 1)]
    dp[0][0] = 0
    for i in range(goods):
        for v in range(max_value + 1):
            if v >= value[i]:
                dp[i + 1][v] = min(dp[i][v], dp[i][v - value[i]] + weight[i])
            else:
                dp[i + 1][v] = dp[i][v]
    answer = 0
    for i in range(max_value):
        if dp[-1][i] <= weight_limit:
            answer = max(answer, i)
    print(answer)


if __name__ == '__main__':
    main()



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

using namespace std;

int N;

struct Pair {
  int m_index;
  int m_value;
  Pair(int index, int value) : m_index{index}, m_value{value} {}
};

vector<Pair> pairs;

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

  cin >> N;
  pairs.reserve(N);
  for (int i = 0; i < N; ++i) {
    int tmp;
    cin >> tmp;
    pairs.emplace_back(i, tmp);
  }

  sort(pairs.begin(), pairs.end(),
       [](Pair lhs, Pair rhs) { return lhs.m_value > rhs.m_value; });

  for (int i = 0; i < N; ++i) {
    if (i == pairs[0].m_index) {
      cout << pairs[1].m_value << endl;
    } else {
      cout << pairs[0].m_value << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 3200
#include <bits/stdc++.h>
#define int long long
#define double long double
#pragma GCC optimize("O3,Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("avx,avx2,sse")
using namespace std;

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

    double x;
    cin >> x;
    double t = x / 3.0;
    cout << fixed << setprecision(10) << t * t * t << '\n';

    fflush(stdout);
    return 0;
}


Measured memory_bytes: 3784
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

n = ni()
a = na()

ans = abs(a[0])
for i in range(n):
    if i == n-1:
        ans += abs(a[i])
        break
    ans += abs(a[i] - a[i+1])

for i in range(n):
    if i == 0:
        print(ans - abs(a[0]) - abs(a[1] - a[0]) + abs(a[1]))
    elif i == n-1:
        print(ans - abs(a[i-1] - a[i]) - abs(a[i]) + abs(a[i-1]))
    else:
        print(ans - abs(a[i-1] - a[i]) - abs(a[i] - a[i+1]) + abs(a[i-1] - a[i+1]))


Measured memory_bytes: 14052
#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define N 10100000
#define INF 214748347
#define po(i,j) ((i-1)*m+j)
using namespace std;
int nxt[N],last[N],date[N],to[N],S,T,ans,d[N],bz[N],tot=1;
void putin(int x,int y,int z)
{
	nxt[++tot]=last[x];last[x]=tot;to[tot]=y;date[tot]=z;
	nxt[++tot]=last[y];last[y]=tot;to[tot]=x;date[tot]=z;
}
bool bfs()
{
	int i=0,j=1;
	memset(bz,0,sizeof(bz));
	bz[d[1]=S]=1;
	while(i<j)
	{
		int x=d[++i];
		for(int k=last[x];k;k=nxt[k]) if(bz[to[k]]==0&&date[k]>0) bz[to[k]]=bz[x]+1,d[++j]=to[k];
	}
	return bz[T]>0;
}
int dfs(int x,int t)
{
	if(x==T) return t;
	int ans=0;
	for(int i=last[x];i;i=nxt[i])
	if(bz[to[i]]==bz[x]+1&&date[i])
	{
		int y=to[i],jy=0;
		jy=dfs(y,min(t,date[i]));
		date[i]-=jy,date[i^1]+=jy,ans+=jy,t-=jy;
		if(t==0) return ans;
	}
	if(ans==0) bz[x]=-1;
	return ans;
}
int main()
{
	int n,m;scanf("%d%d\n",&n,&m);
	S=n+m+1;T=n+m+2;
	fo(i,1,n)
	{
		fo(j,1,m)
		{
			char c=getchar();
			if(c=='o') putin(i,j+n,1);
			if(c=='S') putin(S,i,INF),putin(S,j+n,INF);
			if(c=='T') putin(i,T,INF),putin(j+n,T,INF);
		}
		scanf("\n");
	}
	while(bfs()) ans+=dfs(S,INF);
	if(ans>=INF) ans=-1;
	printf("%d\n",ans);
}

Measured memory_bytes: 49280
#include <string>
#include <iostream>
#include <stack>
#include <queue> // priority_queue も入ってる
#include <set>   // 要素数は size() で取得 multisetもある
#include <map>
#include <array> // sizeはコンパイル時定数で固定
#include <vector>
#include <numeric>   // accumulate, gcd
#include <algorithm> // count_ifに必要
#include <iomanip>   // cout << setprecision(15) << x で小数の出力精度を指定
#include <tuple>
#include <utility> //pair
#include <cmath>

using namespace std;
// 問題が起こるまでintは使用禁止2020-04-13
using ll = long long;

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

template <class InputIterator, class T>
bool contains_itr(InputIterator iterator, const T &value)
{
    if (find(iterator.begin(), iterator.end(), value) == iterator.end())
        return false;
    else
        return true;
}

template <class T>
bool contains_set(set<T> st, const T &value)
{
    if (st.find(value) == st.end())
    {
        return false;
    }
    else
    {
        return true;
    }
}

template <class InputIterator>
auto sum(InputIterator iterator)
{
    return accumulate(iterator.begin(), iterator.end(), 0);
}

// endは排他的(exclusive)なので注意
vector<ll> range(ll begin, ll end)
{
    vector<ll> result;
    for (ll i = begin; i < end; ++i)
    {
        result.push_back(i);
    }
    return result;
}

// =========ここまでテンプレ============

int main()
{
    double a, b, h, m;
    cin >> a >> b >> h >> m;
    double funshin = 6.0 * m * 3.14159265358979323846264338 * 2 / 360;
    double jishin = ((30.0 * h) + 0.5 * m) * 3.14159265358979323846264338 * 2 / 360;
    cout << setprecision(15) << sqrt(a * a + b * b - 2 * a * b * cos(funshin - jishin));
}


Measured memory_bytes: 3644
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


mod = 10**9+7 #出力の制限
N = 10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

n, k = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]
cre_a = sorted(a)
dcre_a = sorted(a, reverse=True)
# print(cre_a)
# print(dcre_a)
m = 0
M = 0
for i in range(n - k + 1):
    m += (cre_a[i] * cmb(n - i - 1, k - 1, mod)) % mod
    m %= mod
for i in range(n - k + 1):
    M += (dcre_a[i] * cmb(n - i - 1, k - 1, mod)) % mod
    M %= mod
ans = (M - m) % mod
print(ans)
# a = cmb(n,r,mod)


Measured memory_bytes: 68836