akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;
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; }
const long long INF = 1LL<<60;

const int MAX_N = 110;
const int MAX_V = 100100;

int N;
long long W, weight[MAX_N], value[MAX_N];
long long dp[MAX_N][MAX_V];

int main() {
    cin >> N >> W;
    for (int i = 0; i < N; ++i) cin >> weight[i] >> value[i];

    for (int i = 0; i < MAX_N; ++i) for (int j = 0; j < MAX_V; ++j) dp[i][j] = INF;

    dp[0][0] = 0;

    for (int i = 0; i < N; ++i) {
        for (int sum_v = 0; sum_v < MAX_V; ++sum_v) {
            if (sum_v - value[i] >= 0) chmin(dp[i+1][sum_v], dp[i][sum_v - value[i]] + weight[i]);
            chmin(dp[i+1][sum_v], dp[i][sum_v]);
        }
    }
    long long res = 0;
    for (int sum_v = 0; sum_v < MAX_V; ++sum_v) {
        if (dp[N][sum_v] <= W) res = sum_v;
    }
    cout << res << endl;
}

Measured memory_bytes: 86272
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string a;
	cin>>a;
	if(a[0]!=a[a.length()-1])
	{
		if((a.length()-1)%2==1) cout<<"Second"<<endl;
		else cout<<"First"<<endl;
	}
	if(a[0]==a[a.length()-1])
	{
		if((a.length()-1)%2==0) cout<<"Second"<<endl;
		else cout<<"First"<<endl;
	}
	return 0;
}

Measured memory_bytes: 512
//#include    <bits/stdc++.h>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <cassert>
#include <iterator>
#include <complex>
#define N  100005
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios::sync_with_stdio(false)
#define INF 0x3f3f3f3f
template<typename T> inline T max(T a,T b,T c){
    return max(a,max(b,c));
}
template<typename T> inline T min(T a,T b,T c){
    return min(a,min(b,c));
}
template<typename T> inline T max(T a,T b,T c,T d){
    return max(a,max(b,c,d));
}
template<typename T> inline T min(T a,T b,T c,T d){
    return min(a,min(b,c,d));
}
const int  dx[]={0,1,0,-1,0,1,-1,1,-1};
const int  dy[]={0,0,1,0,-1,1,-1,-1,1};
typedef long long ll;
using namespace std;
//coding...........................
int parent[N];
struct coordinate
{
    int x;
    int y;
    int id;
}a[N];
struct point
{
    int start;
    int ending;
    int cost;
}b[N*4];

int cmp1(coordinate n,coordinate m)
{
    return n.x<m.x;
}
int cmp2(coordinate n,coordinate m)
{
    return n.y<m.y;
}
int cmp3(point n,point m)
{
    return n.cost<m.cost;
}
int Find(int x)
{
    if(parent[x]==x)
      return x;
    else
      return parent[x]=Find(parent[x]);

}
int main()
{
    int n;
    cin>>n;
    for (int i=1;i<=n;i++)
       {
           cin>>a[i].x>>a[i].y;
           a[i].id=i;
       }
     sort(a+1,a+1+n,cmp1);
     int k=0;
     for (int i=1;i<n;i++)
     {
         b[k].start=a[i].id;
         b[k].ending=a[i+1].id;
         b[k].cost=abs(a[i+1].x-a[i].x);
         k++;
     }
     sort(a+1,a+1+n,cmp2);
     for (int i=1;i<n;i++)
     {
         b[k].start=a[i].id;
         b[k].ending=a[i+1].id;
         b[k].cost=abs(a[i+1].y-a[i].y);
         k++;
     }
     sort(b,b+k,cmp3);
     for (int i=1;i<=n;i++)
        parent[i]=i;
     ll ans=0;
     for (int i=0;i<k;i++)
     {
         int w=Find(b[i].start);
         int v=Find(b[i].ending);
         if (w!=v)
         {
             ans+=b[i].cost;
             parent[w]=v;
         }
     }
     cout << ans << endl;
    return 0;
}


Measured memory_bytes: 6528
#include<bits/stdc++.h>
constexpr long long INFL = 1LL << 60;
constexpr int INF = 1e9;

using namespace std;

using ll = long long;
using P = pair<int, int>;

int main()
{
    int N;
    cin >> N;
    int a[100000];
    for(int i = 0; i < N; ++i) cin >> a[i];
    int cnt4 = 0;
    int cnt2 = 0;
    for(int i = 0; i < N; ++i){
        int tmp = a[i] % 4;
        if(tmp == 0)
            cnt4++;
        else if(tmp == 2)
            cnt2++;
    }

    if(N%2 == 1) N--;

    if(N <= cnt4*2 + cnt2)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}


Measured memory_bytes: 640
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))


def bisearch(S, target):
    left, right = 0, len(S)-1

    while right - left > 0:
        mid = left + (right - left) // 2  # to avoid overflowing by (right + left) > right
        if S[mid] < target:
            left = mid + 1
        else:
            right = mid
    return S[left] == target


count = 0
for t in T:
    count += bisearch(S, t)
print(count)


Measured memory_bytes: 16712
#include <iostream>
#include <string>
using namespace std;

int main()
{
    string s;    
    getline(cin, s);

    for (int i = 0; i < s.length(); i++) {
        if (s[i] < 'A') continue;
        if (s[i] > 'Z') s[i] -= ' ';
        else s[i] += ' ';
    }

    cout << s << endl;

    return 0;
}

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

using namespace std;

typedef long long ll;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;

int main() {
    ll n, m, i, j, k;
    cin >> n;
    vector<vector<ll> > G(n+1);
    for(i=0;i<n-1;i++){
        ll a,b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    vector<ll> c(n);
    for(i=0;i<n;i++){
        cin >> c[i];
    }
    sort(c.begin(),c.end());
    vector<ll> deg(n+1,0);
    queue<ll> pq;
    for(i=1;i<=n;i++){
        deg[i]=(ll)G[i].size();
        if(deg[i]==1){
            pq.push(i);
        }
    }

    ll ret[n+1]={},cnt=0,sum=0;
    while(!pq.empty()){
        ll x = pq.front();
        pq.pop();
        ret[x] = c[cnt++];
        //cout << x << endl;
        for(ll y:G[x]){
            if(ret[y]==0){
                sum+=ret[x];
                deg[y]--;
                if(deg[y]==1){
                    pq.push(y);
                }
            }
        }
    }
    cout << sum << endl;
    for(i=1;i<=n;i++){
        cout << ret[i] << " ";
    }
    cout << endl;
        
    return 0;
}

Measured memory_bytes: 1280
loop {
    s = gets.chomp
    break if s == "#"
    a = s.gsub("north", "N").gsub("west", "W").reverse

    ans = Rational(a[0] == "N" ? 0 : 90, 1)
    (1...a.size).each do |i|
        if a[i] == 'N'
            ans -= Rational(90, 2 ** i)
        else
            ans += Rational(90, 2 ** i)
        end
    end
    puts ans.denominator == 1 ? ans.numerator : ans
}


Measured memory_bytes: 6896
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
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;
}

const long long INF = 1e18;
//const ll mod = 1000000007;

void solve() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }
    string S;
    cin >> S;
    vector<ll> v;
    for(int i = N - 1; i >= 0; i--) {
        ll tmp = A[i];
        if(S[i] == '0') {
            for(auto val : v) {
                chmin(tmp, tmp ^ val);
            }
            if(tmp != 0) {
                v.push_back(tmp);
            }
        } else {
            for(auto val : v) {
                chmin(tmp, tmp ^ val);
            }
            if(tmp != 0) {
                cout << 1 << endl;
                return;
            }
        }
    }
    cout << 0 << endl;
    return;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while(T--) solve();
    return 0;
}


Measured memory_bytes: 3624
#dp[i][j] denotes min weight if possible to obtain value j from first i items
l=input().split()
n=int(l[0])
W=int(l[1])
lweight=[]
lvalue=[]
for i in range(n):
	l=input().split()
	u=int(l[0])
	v=int(l[1])
	lweight.append(u)
	lvalue.append(v)
k=sum(lvalue)
dp=[[-1 for i in range(k+1)] for i in range(n+1)]
for i in range(n+1):
	dp[i][0]=0
for i in range(1,n+1):
	for j in range(1,k+1):
		if(dp[i-1][j]>-1):
			dp[i][j]=dp[i-1][j]
			if(j>=lvalue[i-1] and dp[i-1][j-lvalue[i-1]]!=-1):
				dp[i][j]=min(dp[i][j],dp[i-1][j-lvalue[i-1]]+lweight[i-1])
		elif(j>=lvalue[i-1] and dp[i-1][j-lvalue[i-1]]!=-1):
			dp[i][j]=dp[i-1][j-lvalue[i-1]]+lweight[i-1]
		else:
			dp[i][j]=-1
maxa=0
for i in range(n+1):
	for j in range(k+1):
		if(dp[i][j]!=-1 and dp[i][j]<=W):
			if(j>maxa):
				maxa=j
print(maxa)


Measured memory_bytes: 171784
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int parttion(int A[],char a[],int C[],int p,int r){
    int x=A[r];
    int i=p-1;
    for(int j=p;j<r;j++){
        if(A[j]<=x){
            i++;
            swap(A[i],A[j]);
            swap(a[i],a[j]);
            swap(C[i],C[j]);
        }
    }
    swap(A[i+1],A[r]);
    swap(a[i+1],a[r]);
    swap(C[i+1],C[r]);
    
    return i+1;
}
void quicksort(int A[],char a[],int C[],int p,int r){
    if(p<r){
        int q=parttion(A,a,C,p,r);
        quicksort(A,a,C,p,q-1);
        quicksort(A,a,C,q+1,r);
    }
}
void check(int A[],int C[],int n){
  for(int i=1;i<n;i++){
    if(A[i-1]<A[i])continue;
    if(C[i-1]<C[i])continue;
    cout<<"Not stable"<<endl;
    return;
  }
  cout<<"Stable"<<endl;
}
int main(){
    int n;
    int A[100000]={},C[100000]={};
    char a[100000];
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i]>>A[i];
        C[i]=i;
    }
    quicksort(A,a,C,0,n-1);
    check(A,C,n);
    for(int i=0;i<n;i++){
        cout<<a[i]<<" "<<A[i]<<endl;
    }
    return 0;
}


Measured memory_bytes: 3972
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
#include<stack>
#include<list>

#define endl "\n"
using namespace std;
using ll = long long;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define REP(i, n) for(int i = 0; i < n; i++)
using Graph = vector<vector<int>>;

int main(){
    int a,b,c,k;
    cin>>a>>b>>c>>k;
    if(k <= a) cout<<k<<endl;
    else if(k <= a+b) cout<<a<<endl;
    else cout<< a - (k - a - b) <<endl;
}

Measured memory_bytes: 3652
n, k, q = map(int, input().split())
A = [int(input()) for _ in range(q)]

B = [k-q]*n
for i in range(q):
    B[A[i]-1] += 1

for i in range(n):
    if B[i] <= 0:
        print('No')
    else:
        print('Yes')


Measured memory_bytes: 10472
from itertools import combinations_with_replacement
import sys
input = sys.stdin.readline

n, m, q = map(int, input().split())
abcd = [list(map(int, input().split())) for _ in range(q)]

l = [i for i in range(1, m+1)]
ans = 0
for Alis in combinations_with_replacement(l, n):
    cnt = 0
    for i in range(q):
        if Alis[abcd[i][1] - 1] - Alis[abcd[i][0] - 1] == abcd[i][2]:
            cnt += abcd[i][3]
    ans = max(ans, cnt)

print(ans)


Measured memory_bytes: 9208
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define all(x) (x).begin(),(x).end()
#define V vector
typedef V<int> vi;
typedef V<vi> vvi;
typedef long long ll;
typedef pair<ll, ll> P;
constexpr auto INF = INT_MAX >> 1;
constexpr auto LINF = 5000000000000000;
constexpr auto MOD = 1000000007;

int main() {

	int x;
	cin >> x;
	V<ll> div(0);

	rep1(i, sqrt(x)) {
		if (x % i)continue;
		div.push_back(i);
		div.push_back(x/i);
	}
	
	ll aa = 0, bb = 0;

	rep(i, div.size()) {

		for (ll b = -2000;b < 2000;b++) {
			ll a = b + div[i];
			if (x / div[i] == a * a * a * a + a * a * a * b + a * a * b * b + a * b * b * b + b * b * b * b)
			{
				aa = a;
				bb = b;
				break;
			}
		}

	}

	cout << aa << " " << bb << endl;

}

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

using namespace std;



int main() {

  int N ;cin >> N;
  int A[N],B[N];
  int maxi,second;
  int index;
  maxi = 0;
  for (int i = 0;i<N;i++){
    cin >> A[i];
    if (maxi < A[i]){
      
      maxi = A[i];
      index = i;
    }
  }
  
  memcpy(B,A,sizeof(A));
  sort(B,B+N);
  maxi = B[N-1];
  second = B[N-2];
  
  for (int i=0;i< N;i++){
    if(i != index){
      cout << maxi<< endl;
    }
    else{
      cout<< second << endl;
    }
  }
}

Measured memory_bytes: 3200
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <numeric>
#include <queue>
#include <sstream>
#include <unordered_map>
#include <cstring>
#include <iomanip>

using namespace std;

typedef long long ll;

const ll INF=1e9+7;

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}

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

int main(){
    int A,B;
    string S;
    cin>>A>>B>>S;
    int L=S.length();
    int p=S.find('-')+1;
    int o=S.find('-',A+2);
    if(p!=A+1||o!=-1||L!=A+B+1) cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
    return 0;
}

//a=97,z=122

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

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define inv(n, a) for(int i = 0; i < n; i++) cin >> a[i]
#define MOD 1000000007
#define INF 1e7
#define LINF 1e15
typedef long long ll;
typedef long double ld;
using Graph = vector<vector<int>>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
// 'a' = 97 'z' = 122 => 'a' = 0 'z' = 25

int main() {
    ll n, p; cin >> n >> p;
    vector<ll> a(n);
    inv(n, a);
    int odd = 0;
    rep(i, n){
        if(a[i] % 2 == 1) odd++;
    }
    if(odd == 0 && p == 0){
        cout << (ll)pow(2, n) << endl;
        return 0;
    }else if(odd == 0 && p == 1){
        cout << 0 << endl;
        return 0;
    }
    cout << setprecision(16) << (ll)pow(2, n-1) << endl;
    return 0;
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using ll = long long;
const int MOD = 1000000007;
#define rep(i,n) for (ll i=0; i < (n); i++)
using namespace std;
int get_gcd(int a, int b) {
  while(1) {
    if (a < b) swap(a, b);
    if (b == 0) return a;
    a %= b;
  }
}
int get_lcm(int a, int b){return a * b / get_gcd(a, b);}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main () {
  int n,m;
  scanf("%d %d", &n, &m);

  vector<vector<int>> jobs(100001);
  rep (i,n) {
    int a, b;
    scanf("%d %d", &a, &b);
    jobs[a].push_back(b);
  }

  int ans = 0;
  priority_queue<int> pq;
  // m日後から起算して1日前からm日前（今日）までにかけて
  for (int d = 1; d <= m; d++) {
    // 受けられる候補の追加
    rep(i, jobs[d].size()) {
      pq.push(jobs[d][i]);
    }

    // pqが空でなければ、最大のやつを請ける
    if (!pq.empty()) {
      ans += pq.top();
      pq.pop();
    }
  }

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

  return 0;
}


Measured memory_bytes: 5632
#include <stdio.h>

int main(){
	long long int  k,a,b;
	scanf("%ld %ld %ld",&k,&a,&b);
	int money = 0;
	int cnt = 0;
	long long int num = 1;
	if(a+1<b){
	
		for(cnt = 0;cnt<k;cnt++){
			if(num >= a && (k-cnt)>1){
				num += b-a;
				cnt++;
			}else{
				num++;
			}
		}
	}else{
		num += k;
	}
	printf("%ld\n",num);
	
}


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

int main(void){
    int N,max;
    cin >> N;
    vector<int> score(N);
    max = 0;
    for(int i = 0;i < N;i++){
        cin >> score[i];
        max += score[i];
    }
    for(int i = 0;i < N;i++){
        if(max % 10 != 0)
            break;
        score[i] = max - score[i];
    }

    if(max % 10 == 0){
        max = 0;
        for (int i = 0;i < N;i++){
            max = score[i] > max && score[i] % 10 != 0 ? score[i] : max;
        }
    }
    max = max % 10 == 0 ? 0 : max;
    cout << max << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define INF 1000000000
#define mod 1000000007

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

	ll N,co=0,ans=0,j=0;
	cin>>N;
	VI A(N);
	VI B(N);
	VI C(N,0);
	REP(i,N) cin>>A[i];
	REP(i,N){
		cin>>B[i];
		if(B[i]>A[i]){
			co+=B[i]-A[i];
			ans++;
		}
		else{
			C[j]=A[i]-B[i];
			j++;
		}
	}
	if(ans==0){
		cout<<0<<endl;
		return 0;
	}
	SORT(C);
	ll coo=0;
	for(int i=N-1;i>=0;i--){
		coo++;
		co-=C[i];
		if(co<=0){
			ans+=coo;
			break;
		}
	}
	if(co>0){
		cout<<-1<<endl;
		return 0;
	}
	
	cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 1408
#include <stdio.h>
#include <math.h>
int main()
{
  int a,b;
  char c;
  scanf("%d",&a);
  scanf(" %c",&c);
  scanf("%d",&b);
  while (!((c=='?'))){
    if (c=='+'){
      printf("%d\n",a+b);
    }else if(c=='-'){
      printf("%d\n",a-b);
    }else if(c=='*'){
      printf("%d\n",a*b);
    }else if(c=='/'){
      printf("%d\n",a/b);
    }
    scanf("%d",&a);
    scanf(" %c",&c);
    scanf("%d",&b);
  }
 
 
 
  return 0;
}
 

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

int plu(ll n){
    if(n<0)return (-1)*n;
    else return n;
}
int main(){

    long long a,b,c;
    unsigned long long k;
    cin>>a>>b>>c>>k;
    if(a==b){
        cout<<0<<endl;
        return 0;
    }
    rep(i,k){
        long long INF=1000000000000000000;
        ll aa,bb,cc;
        aa=b+c;
        bb=a+c;
        cc=a+b;
        a=aa;
        b=bb;
        c=cc;
        if(plu(a-b)>INF){
            cout<<"Unfair\n";
            return 0;
        }
    }
    cout<<a-b<<endl;
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define ld long double
using namespace std;
int32_t main()
{
    IOS;
    char c;
    cin>>c;
    if(c<='Z'&&c>='A')
    	cout << "A" <<  endl;
    else
    	cout << "a" << endl;
}

Measured memory_bytes: 3656
#include <bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define lp(i,a,n) for(int i=(a);i<=(int)(n);++i)
#define lpd(i,a,n) for(int i=(a);i>=(int)(n);--i)
#define mem(a,b) memset(a,b,sizeof a)
#define all(v) v.begin(),v.end()
#define println(a) cout <<(a) <<endl
#define sz(x) ((int)(x).size())
#define readi(x) scanf("%d",&x)
#define read2i(x,y) scanf("%d%d",&x,&y)
#define read3i(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define readll(x) scanf("%I64d",&x)
#define mod 1000000007
#define eps 1e-6
#define infi 1000000000
#define infll 1000000000000000000ll
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef set<int> si;
typedef map<int,int> mii;

const int N = 100002;
int n,d1[N],d2[N];
vvi g(N);

void dfs(int i, int p, int d, int dist[]){
    dist[i] = d;
    for(int j : g[i]) if(j != p) dfs(j, i, d+1, dist);
}

int main(){
    readi(n);
    lp(i,1,n-1){
        int x,y;
        read2i(x,y);
        g[x].pb(y);
        g[y].pb(x);
    }

    dfs(1,1,0,d1);
    dfs(n,n,0,d2);

    int x = 0, y = 0;
    lp(i,1,n){
        if(d1[i] <= d2[i]) ++x;
        else ++y;
    }
    println(x > y ? "Fennec" : "Snuke");
}

/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
ios::sync_with_stdio(0);cin.tie(0);
*/


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

long long ans = 0;

void brute (long long a, long long b) {
    if (b == 0) return;
    ans += a/b * 2 * b;
    if (a%b == 0) ans -= b;
    brute(b, a%b);
}

int main() {
    long long x, n;
    cin >> n >> x;
    brute(max(x,n-x),min(x,n-x));
    cout << ans + n;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
public class Aprob {
    public static void Main() {
        string[] readSome = new string[3];
        readSome = Console.ReadLine().Split(' ');
        int[] N = new int[3];
        for (int i = 0; i < 3; i++) {
            N[i] = int.Parse(readSome[i]);
        }
        string outp = "NO";
        if (N[1] - N[0] == N[2] - N[1]) {
            outp = "YES";
        }
        Console.WriteLine(outp);
    }
}

Measured memory_bytes: 11092
from sys import exit
import math
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
s = [input() for i in range(n)]

judge = ["AC", "WA", "TLE", "RE"]
ans = [0]*4
for i in range(n):
    for j in range(4):
        if s[i] == judge[j]:
            ans[j] += 1

for i in range(4):
    print(judge[i] + " x " + str(ans[i]))


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

#define Abigail inline void
typedef long long LL;

const int N=15,INF=(1<<30)-1;

int n,m,e[N+9][N+9],sum;
int a[(1<<N)+9];

void Get_a(){
  for (int g=1;g<1<<n;++g)
    for (int i=0;i<n;++i){
    	if (g>>i&1^1) continue;
    	for (int j=i+1;j<n;++j)
    	  if (g>>j&1) a[g]+=e[i][j];
		}
} 

int b[N+9][(1<<N)+9];

void Get_b(){
  for (int g=1;g<1<<n;++g)
  	for (int i=0;i<n;++i){
  		if (g>>i&1) continue;
  	  b[i][g]=a[g];
  		for (int j=0;j<n;++j)
  		  if (g>>j&1) b[i][g]+=e[i][j];
		}
}

int dp[N+9][(1<<N)+9];

void Get_dp(){
  for (int i=0;i<n;++i)
    for (int g=0;g<1<<n;++g) dp[i][g]=-INF;
  dp[0][1]=0;
  for (int g1=1;g1<1<<n;++g1)
  	for (int i=0;i<n;++i){
  		if (dp[i][g1]==-INF) continue;
  		int t=~g1&(1<<n)-1;
  		for (int g2=t;g2;g2=g2-1&t)
  			dp[i][g1|g2]=max(dp[i][g1|g2],dp[i][g1]+b[i][g2]);
  		for (int j=0;j<n;++j)
  		  if (g1>>j&1^1&&e[i][j]){
				  dp[j][g1|1<<j]=max(dp[j][g1|1<<j],dp[i][g1]+e[i][j]);
				}
		}
}

Abigail into(){
  scanf("%d%d",&n,&m);
  for (int i=1;i<=m;++i){
  	int x,y,v;
  	scanf("%d%d%d",&x,&y,&v);--x;--y;
  	e[x][y]=e[y][x]=v;
  	sum+=v;
	}
}

Abigail work(){
  Get_a();
  Get_b();
  Get_dp();
}

Abigail outo(){
  printf("%d\n",sum-dp[n-1][(1<<n)-1]);
}

int main(){
  into();
  work();
  outo();
  return 0;
}

Measured memory_bytes: 6528
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
#define forinc(i,a,b) for(int i=a;i<=b;i++)
#define fordec(i,a,b) for(int i=a;i>=b;i--)
#define pii pair<int,int>
#define fi first
#define se second

const int maxn=2e5+10;
int n,h[maxn],a[maxn];
int f[maxn],it[4*maxn];
void update(int s,int l,int r,int u,int x)
{
    if(u>r||u<l) return;
    if(l==r)
    {
        it[s]=max(it[s],x);
        return;
    }
    int mid=(l+r)/2;
    update(2*s,l,mid,u,x);
    update(2*s+1,mid+1,r,u,x);
    it[s]=max(it[2*s],it[2*s+1]);
}
int get(int s,int l,int r,int u,int v)
{
    if(u>r||l>v) return 0;
    if(u<=l&&r<=v) return it[s];
    int mid=(l+r)/2;
    return max(get(2*s,l,mid,u,v),get(2*s+1,mid+1,r,u,v));

}
main()
{
    cin>>n;
    forinc(i,1,n) cin>>h[i];
    forinc(i,1,n) cin>>a[i];
    f[1]=a[1];
    update(1,1,n,h[1],a[1]);
    forinc(i,2,n)
    {
        f[i]=get(1,1,n,1,h[i]-1)+a[i];
        //cout<<get(1,1,n,1,h[i]-1)<<" "<<h[i]<<"\n";
        update(1,1,n,h[i],f[i]);
        //cout<<f[i]<<" "<<h[i]<<"\n";
    }
    //return 0;
    int ret=0;
    forinc(i,1,n){
     //   cout<<f[i]<<" ";
        ret=max(ret,f[i]);
    }
    cout<<ret;
}


Measured memory_bytes: 11136
gets

weights = gets.split.map(&:to_i)

min = 9999999999
(weights.size - 1).times do |i|
  s1 = weights[0..i].inject(&:+)
  s2 = weights[i+1..-1].inject(&:+)
  if (s1 - s2).abs < min
    min = (s1 - s2).abs
  end
end

puts min

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(V) V.begin(),V.end()
const ll MOD = 1000000007;

int main(){
	int H, W;
	cin >> W >> H;
	vector<ll> P(W), Q(H);
	for (int i = 0;i < W;i++) {
		cin >> P[i];
	}
	for (int i = 0;i < H;i++) {
		cin >> Q[i];
	}
	P.push_back(MOD);
	Q.push_back(MOD);

	//よくわかるクラスカル法 以上！w
	sort(all(P));
	sort(all(Q));
	ll h = H + 1, w = W + 1, hi = 0, wi = 0;
	ll ans = 0;
	while (hi < H || wi < W) {
		if (P[wi] < Q[hi]) {
			ans += P[wi] * h;
			w--;
			wi++;
		}
		else {
			ans += Q[hi] * w;
			h--;
			hi++;
		}
	}
	cout << ans << endl;
}

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


int main()
{
    int n; cin >> n;
    cout << (1000 - (n % 1000)) % 1000 << endl;
}

/*
Ctrl+@
g++ a.cpp
./a.out
*/

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

vi pos[245555];
int nxt[20][245555];
int n2[55][240001];
int a[240111];
int S[222222];
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; ll k; cin>>n>>k;
	for(int i=0;i<n;i++)
	{
		cin>>a[i]; pos[a[i]].pb(i);
	}
	for(int i=0;i<=222222;i++)
	{
		for(int j=0;j<pos[i].size();j++)
		{
			nxt[0][pos[i][j]]=pos[i][j];
			if(j+1<pos[i].size()) nxt[0][pos[i][j]]=pos[i][j+1]+1;
		}
	}
	nxt[0][n]=n;
	for(int i=1;i<20;i++)
	{
		for(int j=0;j<=n;j++)
		{
			nxt[i][j]=nxt[i-1][nxt[i-1][j]];
		}
	}
	int posinit=nxt[19][0];
	n2[0][n]=posinit;
	for(int i=0;i<n;i++)
	{
		int startpos=pos[a[i]][0];
		if(startpos==n-1) n2[0][i]=n;
		else n2[0][i]=nxt[19][startpos+1];
		//cerr<<i<<' '<<n2[0][i]<<'\n';
	}
	//cerr<<n<<' '<<n2[0][n]<<'\n';
	for(int i=1;i<55;i++)
	{
		for(int j=0;j<=n;j++)
		{
			n2[i][j]=n2[i-1][n2[i-1][j]];
		}
	}
	int cur=n;
	k--;
	for(int i=0;i<55;i++)
	{
		if(k&(1LL<<i)) cur=n2[i][cur];
	}
	int startpos = 0;
	if(cur<n) startpos=pos[a[cur]][0]+1;
	vi vec;
	for(int i=startpos;i<n;i++)
	{
		if(!S[a[i]])
		{
			S[a[i]]=1; vec.pb(a[i]);
		}
		else
		{
			while(vec.back()!=a[i])
			{
				S[vec.back()]=0; vec.pop_back();
			}
			S[a[i]]=0; vec.pop_back();
		}
	}
	for(int i=0;i<vec.size();i++)
	{
		cout<<vec[i];
		if(i+1<vec.size()) cout<<' ';
	}
	cout<<'\n';
}


Measured memory_bytes: 86776
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, a, b) for(int i = a; i < b; i++)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
using P = pair<int,int>;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }

int main(){
    int n;
    string s;
    cin >> n >> s;
    vector<int> kuro(n), siro(n);
    if (s[0] == '#') kuro[0] = 1;
    else siro[0] = 1;
    for(int i = 1; i < n; i++){
         if (s[i] == '#') {
             kuro[i] = kuro[i-1] + 1;
             siro[i] = siro[i-1];
         }
         else{
             kuro[i] = kuro[i-1];
             siro[i] = siro[i-1] + 1;
         } 
    }

    int ans = n;
    for(int i = 0; i < n; i++){
        int ope;
        if (i == 0){
            ope = min(siro[n-1], kuro[n-1]);
        }
        else{
            ope = min(kuro[i-1], siro[i-1]) + (siro[n-1] - siro[i-1]);
        }
        ans = min(ans, ope);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5260
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using P=pair<ll,ll>;
#define MOD 1000000007ll
#define INF 1000000000ll
#define EPS 1e-10
#define FOR(i,n,m) for(ll i=n;i<(ll)m;i++)
#define REP(i,n) FOR(i,0,n)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v) sort(ALL(v));v.erase(unique(ALL(v)),v.end());
#define pb push_back

ll _pow(ll a, ll n) {
	if(n==0) return 1;
	else {
		ll res = 1;
		ll buf = a;
		while(n>0) {
			if(n%2==1) {
				res *= buf;
				res %= MOD;
			}
			buf *= buf;
			buf %= MOD;
			n/=2;
		}
		return res;
	}
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll l;
	cin>>l;
	bitset<20> bi(l);
	ll cnt=0;
	REP(i,20) if(bi[i]) cnt=i;
	ll n=cnt+1;
	ll m=2*(n-1);
	vector<pair<P,ll>> edg;
	REP(i,n-1) {
		edg.pb(make_pair(P(i+1,i+2),0));
		edg.pb(make_pair(P(i+1,i+2),_pow(2,(cnt-1-i))));
	}
	ll sum=0;
	for(ll i=cnt; i>=0; i--) {
		if(bi[i]&&i!=cnt) {
			m++;
			edg.pb(make_pair(P(1,n-i),sum));
		}
		if(bi[i]) sum+=_pow(2,i);
	}
	cout<<n<<" "<<m<<endl;
	REP(i,m) {
		cout<<edg[i].first.first<<" "<<edg[i].first.second<<" "<<edg[i].second<<endl;
	}
	return 0;
}


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

using namespace std;

#define INF 1000000007
#define LINF (1LL << 61)
#define PI 3.14159265358979

typedef long long i64;
typedef pair<i64,i64> P;

inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }

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



int a,b,c,d,e;
void solve(){
	cin >> a >> b >> c >> d >> e;
	
	int cnt = (c-a)*60 - (b-d);
	cout << max(cnt-e,0) << endl;
}

int main(){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

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

#define REP(i, n) for(int (i)=0;(i)<(n);++(i))
#define MOD 1000000007

using namespace std;

typedef long long ll;

int main()
{
    int ans = 0;
    int N;
    cin >> N;
    ll a;
    REP(i, N)
    {
        cin >> a;
        while (a % 2 == 0)
        {
            ans++;
            a /= 2;
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int K = scanner.nextInt();

		int sum = 0;
		for (int i = 1; i <= K; i++) {
			for (int j = 1; j <= K; j++) {
				for (int k = 1; k <= K; k++) {
					sum += gcd(i, j, k);
				}
			}
		}

		System.out.println(sum);
	}

	public static int gcd(int x, int y) {
		if (y == 0)
			return x;

		return gcd(y, x % y);
	}

	public static int gcd(int x, int y, int z) {
		return gcd(gcd(x, y), z);
	}
}

Measured memory_bytes: 35896
function Main(input) {
  input = input.split("\n");
  var n = parseInt(input[0].split(" ")[0]);
  var k = parseInt(input[0].split(" ")[1]);
  x = new Array(n).fill(0);
  tmp = input[1].split(" ");
  var plus=0;
  var minus=0;
  for(i=0;i<n;i++){
    x[i]=parseInt(tmp[i]);
    if(x[i]>0){
      plus++;
    }else if(x[i]<0){
      minus++;
    }
  }
  var ans=Math.pow(10,9)+7;
  if(x.indexOf(0)!=-1){
    n-=1;
    k-=1;
    x.splice(x.indexOf(0),1);
  }
  if(x.length==0){
    ans=0;
  }else if(minus==0){
    ans=x[k-1];
  }else if(plus==0){
    ans=Math.abs(x[n-k]);
  }else if(n!=2){
    for(i=0;i<n-k+1;i++){
      if(x[i]<0&&x[i+k-1]>0){
        ans=Math.min(ans,Math.abs(x[i])*2+x[i+k-1],Math.abs(x[i])+x[i+k-1]*2);
      }else if(i==minus-k){
        ans=Math.min(ans,Math.abs(x[i]));
      }else if(i==minus){
        ans=Math.min(ans,x[i+k-1]);
      }
    }
  }else{
    ans=Math.min(Math.abs(x[0]),x[1]);
  }
  console.log('%s', ans);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

#define INF (2e9)
#define FOR(i, a, b) for (ll (i) = (a); (i) < (b); ++(i))
#define REP(i, n) FOR(i, 0, n)

using namespace std;

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

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

using ll = long long;
using ld = long double;

#define ALL(x) (x).begin(), (x).end()
template<class T>
using vc = vector<T>;
using vi = vc<ll>;
using vvi = vc<vi>;

template<class T>
using va = valarray<T>;
using vad = va<ld>;
using vai = va<ll>;

using pii = pair<ll, ll>;

vi Read(ll n) {
    auto      v = vi(n);
    for (auto i = std::size_t(0); i < n; ++i) {
        cin >> v[i];
    }
    return v;
}

template<class T>
void DumpRow(const T& A) {
    for (const auto& value : A)
        cout << value << "\n";
}

template<class T>
void DumpColumn(const T& A) {
    auto isFirst = true;
    for (const auto& value : A) {
        if (isFirst) {
            cout << value;
            isFirst = false;
        } else {
            cout << " " << value;
        }

    }
    cout << endl;
}

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

    ll n;
    cin >> n;
    const auto v = Read(n);

    ll q;
    cin >> q;
    const auto k = Read(q);
    REP(i, q){
        cout << binary_search(ALL(v), k[i]) << "\n";
    }
    return 0;
}



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

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(lol i=0;i<lol(n);i++)
#define REPD(i,n) for(lol i=n-1;i>=0;i--)
#define FOR(i,a,b) for(lol i=a;i<=lol(b);i++)
#define FORD(i,a,b) for(lol i=a;i>=lol(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end() //sortなどの引数を省略したい
#define SIZE(x) lol(x.size()) //sizeをsize_tからllに直しておく
//定数
#define PI 3.1415926535897932385 //pi
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//最大値最小値
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int main()
{
    lol index, kabu;
    lol result{1000};
    lol n; cin >> n;
    vector<lol> a(n+5, -1);
    REP(i, n)
    {
        cin >> a[i];
    }
    FOR(i, 0, n-2)
    {
        kabu = 0;
        if(a[i] < a[i + 1])
            kabu = result / a[i];
        result += (a[i + 1] - a[i]) * kabu;
        //cout << result << endl;
    }

    cout << result << endl;
    return 0;
}

Measured memory_bytes: 3636
#include<iostream>
using namespace std;int n,m,g,d,l[10],f,i,j,y,x;string p[30];int c(){for(y=n;y-->0;)l[y]=y+1;for(;++y<d;)for(x=n-1;x-->0;)if(p[y][x]^48)swap(l[x],l[x+1]);return l[g-1]==m;}main(){for(;cin>>n>>m>>g>>d;f-1?puts(f?"0":"1"):printf("%d %d\n",i,j)){for(i=0;i<d;)cin>>p[i++];f=c()*2;for(i=0;!f & i<d;i++)for(j=0;!f & j<n-1;j++)if(p[i][j]-49&p[i][j-1]-49&p[i][j+1]-49){p[i][j]++,f=c(),p[i][j]--;};}}

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

map<ll,ll> ma;

int main(){
    ll n,m,x=0,ans=0;
    cin>>n>>m;
    ma.emplace(0,1);
    for(ll i=0;i < n;i++)
    {
        ll in;cin>>in;
        x+=in;x%=m;    
        if(ma.count(x)) ma.at(x)++;
        else ma.emplace(x,1); 
        ans+=ma.at(x)-1;
    }
    cout << ans << endl;
}

Measured memory_bytes: 4224
import sys
import math
import fractions
import bisect
import queue
import heapq
import collections
import itertools
import random
sys.setrecursionlimit(4100000)


D = int(input())
C = list(map(int,input().split()))

S = []
for i in range(D):
    tmp = list(map(int,input().split()))
    S.append(tmp)


class Schejule:

    def __init__(self, sche):
        self.base = sche
        self.last = [0] * 26
        self.y = 0

    def get_score(self):
        self.y = 0
        for d in range(D):
            self.y += S[d][self.base[d]]

        for d in range(D):
            self.last[self.base[d]] = d + 1

            for j in range(26):
                self.y -= C[j] * (d+1 - self.last[j])

    def change_one(self, day, to):

        org = self.base[day]

        # 差分
        div = 0

        # その日の満足度の変化
        div += S[day][to] - S[day][org]

        # 損失
        org_loss = 0
        cha_loss = 0

        org_last = 0
        cha_last = 0
        for d in range(D):
            if self.base[d] == org:
                org_last = d + 1
            elif self.base[d] == to:
                cha_last = d + 1

            org_loss +=  C[org] * (d+1 - org_last)
            cha_loss +=  C[to ] * (d+1 - cha_last)

        def_loss = cha_loss + org_loss


        org_loss = 0
        cha_loss = 0

        org_last = 0
        cha_last = 0
        for d in range(D):
            if d != day:
                if self.base[d] == org:
                    org_last = d + 1
                elif self.base[d] == to:
                    cha_last = d + 1
            else:
                cha_last = d+1

            org_loss +=  C[org] * (d+1 - org_last)
            cha_loss +=  C[to ] * (d+1 - cha_last)

        aft_loss = cha_loss + org_loss


        # 全体の差分
        div -= aft_loss - def_loss

        # ε-greedy
        if div > 0 or random.randint(0, 9) >= 4:
            next_plan = self.base
            next_plan[day] = to

            sche_next = Schejule(next_plan)
            sche_next.y = self.y + div

            return sche_next
        else:
            return self



T = [0] * D

for i in range(D):
    max_day = 0
    for j in range(26):
        if S[i][max_day] < S[i][j]:
            max_day = j
    T[i] = max_day


sche_base = Schejule(T)
sche_base.get_score()


best_score = sche_base.y
best_set = sche_base.base.copy()

#print(sche_base.y)

#print(*sche_base.base)

for i in range(1000):
    d = random.randint(0, D - 1)
    t = random.randint(0, 26 - 1)

    sche_base  = sche_base.change_one(d, t)

    if best_score < sche_base.y:
        best_score = sche_base.y
        best_set = sche_base.base.copy()
        #print("updated!!!!")

    #print("now: ", sche_base.y, "->", *sche_base.base)
    #print("best:", best_score, "->", *best_set)
    #print("\n")
    #print(*sche_base.base)

    #print(sche_base.y)

for i in range(D):
    print(best_set[i] + 1)










Measured memory_bytes: 79648
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define MOD (1000000007)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define all(a)  (a).begin(),(a).end()

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

int gcd(int a, int b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

const ll INF = 1LL << 60;

int main(){
  int n; string s; cin >> n >> s;

  map<char, int> C;
  rep(i, n) C[s[i]]++;

  ll ans = 1;
  for(auto it : C){
    int num = it.second;
    ans *= (num+1);
    ans %= MOD;
  }

  std::cout << ans-1 << '\n';
}


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

int main() {
  string s;
  cin >> s;
  string ans = "";
  for (char x : s) {
    if (x == '0') ans.push_back('0');
    if (x == '1') ans.push_back('1');
    if (x == 'B' && ans.size()) ans.pop_back();
  }
  cout << accumulate(ans.begin(), ans.end(), string()) << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <vector>
#include <cfloat>
#include <string>
#include <cmath>
#include <set>
#include <cstdlib>
#include <map>
#include <ctime>
#include <iomanip>
#include <functional>
#include <deque>
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#include <stack>
#include <climits>
#include <sys/time.h>
#include <cctype>

using namespace std;

typedef long long ll;

// ll:9187201950435737471 int:2139062143
#define setinf(x) memset((x), 127, sizeof(x))
#define MAX_V 10000

class DisjointSet {
public:
  vector <int> rank, p;
  
  DisjointSet() {}
  DisjointSet(int size) {
    rank.resize(size, 0);
    p.resize(size, 0);
    for (int i = 0; i < size; i++) makeSet(i);
  }

  void makeSet(int x) {
    p[x] = x;
    rank[x] = 0;
  }

  bool same(int x, int y) {
    return findSet(x) == findSet(y);
  }

  void unite(int x, int y) {
    link(findSet(x), findSet(y));
  }

  void link(int x, int y) {
    if (rank[x] > rank[y]) {
      p[y] = x;
    }else {
      p[x] = y;
      if (rank[x] == rank[y]) {
	rank[y]++;
      }
    }
  }

  int findSet(int x) {
    if (x != p[x]) {
      p[x] = findSet(p[x]);
    }
    return p[x];
  }
};

class edge {
public:
  int from, to, cost;
  edge(int from = 0, int to = 0, int cost = 0): from(from), to(to), cost(cost) {}
  bool operator < (const edge &e) const {
    return cost > e.cost;
  }
};

bool comp(const edge &e1, const edge &e2) {
  return e1.cost < e2.cost;
}

int V, E;
vector <edge> graph[MAX_V];

int solve() {
  int mincost[V];
  bool used[V];
  memset(used, false, sizeof(used));
  setinf(mincost);
  mincost[0] = 0;
  int ret = 0;

  priority_queue<edge> pque;
  for (int i = 0; i < graph[0].size(); i++) {
    pque.push(graph[0][i]);
  }
  used[0] = true;
  while (true) {
    while (!pque.empty() && used[pque.top().to]) pque.pop();
    if (pque.empty()) break;

    int p = pque.top().to;
    used[p] = true;
    ret += pque.top().cost;
    pque.pop();
    for (int i = 0; i < graph[p].size(); i++) {
      edge e = graph[p][i];
      if (used[e.to]) continue;
      pque.push(e);
    }
  }

  return ret;
}

int main() {
  cin >> V >> E;
  for (int i = 0; i < E; i++) {
    int s, t, w;
    cin >> s >> t >> w;
    graph[s].push_back(edge(s, t, w));
    graph[t].push_back(edge(t, s, w));
  }
  cout << solve() << endl;
}

Measured memory_bytes: 6952
# ABC 077
def getInt(): return int(input())
def zeros(n): return [0]*n

N = getInt()
l = zeros(N+1)
l[0],l[1] = 2,1
for i in range(2,N+1):
    l[i] = l[i-1]+l[i-2]
print(l[N])

Measured memory_bytes: 3060
N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))
max_A = max(A)
max_index = A.index(max_A)
A.pop(max_index)
next_max = max(A)
for i in range(N):
    if i == max_index:
        print(next_max)
    else:
        print(max_A)


Measured memory_bytes: 12512
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;
 
const ll nmax = 1e9 + 7;
const ll Mod = 998244353;
const double PI = 2 * asin(1);

int N, M, ans;
vector <int> Graph[8];
bool visited[8];

int DFS(int Node, int turn){
  if (turn == N - 1){
    ans++; return 0;
  }

  visited[Node] = true;
  for (int i = 0; i < Graph[Node].size(); i++){
    int next = Graph[Node][i];
    if (!visited[next]){
      DFS(next, turn + 1);
    }
  }
  visited[Node] = false;
  return 0;
}

int main(){
  cin >> N >> M;
  for (int i = 0; i < M; i++){
    int A, B; cin >> A >> B;
    A--; B--;
    Graph[A].push_back(B);
    Graph[B].push_back(A);
  }
  visited[0] = true;
  DFS(0, 0);
  cout << ans << endl;
  
  return 0;
}


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

int main(){
	int n;
	while(cin >> n){
		if(n == 0) break;
		else{
			int data[n+2][n+2];

			for (int i = 0; i < n+2; ++i){
				for(int j = 0; j < n+2; j++){					
				data[i][j] = 0;
				}
			}
			
			for (int i = 0; i < n; ++i){
				for(int j = 0; j < n; j++){					
				cin >> data[i][j];
				}
			}
			for (int i = 0; i < n; ++i){
				for(int j = 0; j < n; j++){	
					data[i][n] += data[i][j];
				}
			}
			for (int i = 0; i < n+1; ++i){
				for(int j = 0; j < n; j++){	
					data[n][i] += data[j][i];
				}
			}
			for (int i = 0; i < n+1; ++i){
				for(int j = 0; j < n+1; j++){
					cout.width(5);
					cout << data[i][j];
					// if (j != n) cout<<" ";
				}
				cout << endl;
			}
				
		}
	}
	return 0;
}

Measured memory_bytes: 1176
n = gets.to_i
r = []

n.times do |i|
  r[i] = gets.to_i
end

min = r[0]
max = r[1] - r[0]

1.upto(r.size-1) do |i|
  max = max < r[i] - min ? r[i] - min : max
  min = min > r[i] ? r[i] : min
end

puts max


Measured memory_bytes: 8888
#include <iostream>
#include <string.h>
#include <bits/stdc++.h>
#include<algorithm> 
using namespace std;

int main() {
int N, K;
cin >> N >> K;
int a[N];

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

if(N == 1){
	if(a[0] < K) cout << 0 << endl;
	else cout << 1 << endl;
	return 0;
}

long int dp[N][K+1];

for (int i = 0; i < N; ++i)
{
	for (int j = 0; j <= K; ++j)
	{
		dp[i][j] = 0;
	}
}

for (int i = 0; i <= a[0]; ++i)
{
	dp[0][i] = 1;
}

for (int i = 1; i <= K; ++i)
{
	dp[0][i] = (dp[0][i] +  dp[0][i-1])%1000000007;
}

for (int i = 1; i < N; ++i)
{
	for (int j = 0; j <= K; ++j)
	{	
		if(j <= a[i])
		dp[i][j] = (j > 0) ? (dp[i][j-1] + dp[i-1][j])%1000000007 : dp[i-1][j]%1000000007;
		else dp[i][j] = (dp[i][j] + dp[i][j-1] + dp[i-1][j]-(dp[i-1][j-1-a[i]]) + 1000000007)%1000000007;
	}
}
if(K != 0)
cout << (dp[N-1][K] - dp[N-1][K-1] + 1000000007)%1000000007<< endl;
else cout << dp[N-1][K]%1000000007 << endl;

return 0;
                                                     
}

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

ll N, P;

vector<ll> primeFactorization(ll n) {
    vector<ll> ret;
    ll a = 2;
    while (n >= a * a) {
        if (n % a == 0) {
            ret.push_back(a);
            n /= a;
        } else {
            a++;
        }
    }
    ret.push_back(n);
    return ret;
}

int main() {
    cin >> N >> P;

    vector<ll> pf = primeFactorization(P);

    ll ans = 1;
    ll now = pf[0];
    ll cnt = 1;
    for (int i = 1; i < pf.size(); i++) {
        if (now == pf[i]) {
            cnt++;
        }
        else {
            if (cnt / N > 0) ans *= (ll)pow(now, cnt / N);            
            now = pf[i];
            cnt = 1;
        }
    }
    if (cnt / N > 0) ans *= (ll)pow(now, cnt / N); 

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define mem(a,n) memset(a,n,sizeof(a))
#define rep(i,a,n) for(int i=a;i<n;i++)
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
const double eps=1e-6;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=100+5;
char s[N];
int main()
{
    int a,b;
    while(~scanf("%d%d",&a,&b))
    {
        scanf("%s",s);
        int len=strlen(s);
        bool flag=0;
        rep(i,0,len)
        {
            if(i==a)
            {
                if(s[i]!='-')
                {
                    flag=1;
                    break;
                }
            }
            else
            {
                if(!isdigit(s[i]))
                {
                    flag=1;
                    break;
                }
            }
        }
        printf("%s\n",flag?"No":"Yes");
    }
    return 0;
}


Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

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

#define rep(i,n) for(int64_t i = 0;i < n;i++)
using ll = int64_t;
template<class T> bool chmin(T& a,T b){
    if(a > b){ a = b; return true; }else return false;
}
template<class T> bool chmax(T& a,T b){
    if(a < b){ a = b; return true; }else return false;
}

using ld = long double;

class ICoins {
public:
	void solve(std::istream& cin, std::ostream& cout) {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);

        int64_t n;cin >> n;
        vector<ld> p(n);
        rep(i,n)cin >> p[i];
        vector<vector<ld>> dp(n+1,vector<ld>(n+1,0.0));

        dp[0][0] = 1.00;

        rep(i,n)rep(j,i+1){
            dp[i+1][j+1] += dp[i][j] * p[i];
            dp[i+1][j] += dp[i][j] * (1.00 - p[i]);
        }

        ld ans = 0.0;
        for(int i = (n+1)/2;i <= n;i++)ans += dp[n][i];
        cout << ans << '\n';

        //int t;cin >> t;rep(i,t)main2(cin,cout);
	}
	void main2(istream& cin,ostream& cout){

	}
};


int main() {
	ICoins solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 141056