akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <map>
#include <stack>
#define f first
#define s second
using namespace std;
typedef pair<int, int> p;
typedef pair<int, p> pp;
// 0=white, 1=black
int main() {
    int n;
    while (scanf("%d",&n)) {
        if (!n) break;
        stack<pp> list;
        int in; scanf("%d", &in);
        list.push(make_pair(in, make_pair(0, 1)));
        for (int i=1; i<n; i++) {
            scanf("%d",&in);
            if (i%2!=0) {
                pp bef=list.top(); list.pop();
                // printf("%d %d %d\n", bef.f, bef.s.f, bef.s.s);
                if (bef.f==in) {
                    bef.s.s++;
                    list.push(bef);
                } else {
                    if (list.empty()) {
                        bef.f=in;
                        bef.s.s++;
                        list.push(bef);
                    } else {
                        pp bef2=list.top(); list.pop();
                        bef2.s.s=bef.s.s+1;
                        list.push(bef2);
                    }
                }
            } else {
                pp bef=list.top();
                // printf("%d %d %d\n", bef.f, bef.s.f, bef.s.s);
                if (bef.f==in) {
                    list.pop();
                    bef.s.s++;
                    list.push(bef);
                } else {
                    list.push(make_pair(in, make_pair(i, i+1)));
                }
            }
        }
        int res=0;
        while (!list.empty()) {
            pp x=list.top(); list.pop();
            // printf("%d %d %d\n",x.f,x.s.f,x.s.s);
            if (!x.f) res+=x.s.s-x.s.f;
        }
        printf("%d\n",res);
    }
}

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

#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define REACH cerr<<"reached line "<<__LINE__<<endl
#define DBG(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl

using uint=unsigned int;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"[";
	REP(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"]";
	return os;
}

int read(){
	int i;
	scanf("%d",&i);
	return i;
}

void Yes(){
	cout<<"Yes"<<endl;
	exit(0);
}

void No(){
	cout<<"No"<<endl;
	exit(0);
}

template<class T>
void chmax(T& a,T b){
	a=max(a,b);
}

template<class T>
void chmin(T& a,T b){
	a=min(a,b);
}

template<class T>
void ResetVector(vector<T>& v,int n,const T& t){
	v.clear();
	v.resize(n,t);
}

const int mod=924844033;
template<class T,class U>
void add(T& a,U b){
	a=((ll)a+b)%mod;
}

template<>
void add(int& a,int b){
	a+=b;
	if(a>=mod)a-=mod;
}

template<class T,class U>
void sub(T& a,U b){
	a=((ll)a-b%mod+mod)%mod;
}

template<>
void sub(int& a,int b){
	a-=b;
	if(a<0)a+=mod;
}

template<class T,class U>
void mult(T& a,U b){
	a=((ll)a*b)%mod;
}

ll modPow(ll a,ll p){
	ll s=1;
	REP(i,30){
		if((p>>i)&1)
			mult(s,a);
		mult(a,a);
	}
	return s;
}

ll modInv(ll a){
	return modPow(a,mod-2);
}

const int dpMax=2114;
ll fact[dpMax];
ll dp1[dpMax][2],dp2[dpMax];

int main(){
	fact[0]=1;
	FOR(i,1,dpMax)
		fact[i]=fact[i-1]*i%mod;
	int n=read(),k=read();
	vector<bool> vis(2*n,false);
	vi cs(n+1,0);
	REP(i,2*n)if(!vis[i]){
		int c=0,j=i;
		while(j/2<n){
			vis[j]=true;
			c++;
			j=((j/2)+k)*2+((j&1)^1);
		}
		cs[c]++;
	}
	dp1[0][0]=1;
	dp2[0]=1;
	FOR(i,1,n+1){
		REP(_,cs[i])
			for(int j=dpMax-1;j>=0;j--){
				for(int t=min(i,j);t>=1;t--)
					add(dp2[j],dp2[j-t]*(dp1[t][0]+dp1[t][1]));
			}
		for(int t=i;t>=0;t--){
			dp1[t][0]=(dp1[t][1]+dp1[t][0])%mod;
			dp1[t][1]=dp1[t-1][0];
		}
	}
	ll ans=0;
	REP(i,n+1)
		if(i%2==0)
			add(ans,dp2[i]*fact[n-i]);
		else
			sub(ans,dp2[i]*fact[n-i]);
	cout<<ans<<endl;
}


Measured memory_bytes: 256
def Base_10_to_n(X, n):
    if (int(X/n)):
        return Base_10_to_n(int(X/n), n)+str(X%n)
    return str(X%n)

N,K = map(int, input().split())

toN = Base_10_to_n(N,K)
print(len(toN))

Measured memory_bytes: 3060
using System.Linq;
using static System.Math;
using System;

public class hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var m = int.Parse(line[0]);
        var n = int.Parse(line[1]);
        var p = new int[m];
        var c = new int[n];
        var e = new int[n];
        for (int i = 0; i < m; i++) p[i] = int.Parse(Console.ReadLine().Trim());
        Array.Sort(p);
        Array.Reverse(p);
        for (int i = 0; i < n; i++)
        {
            line = Console.ReadLine().Trim().Split(' ');
            c[i] = int.Parse(line[0]);
            e[i] = int.Parse(line[1]);
        }
        var dp = getDP(c, e, m, n);
        var ans = getAns(dp, p, m, n);
        Console.WriteLine(ans);
    }
    static int getAns(int[,] dp, int[] p, int m, int n)
    {
        var ans = 0;
        var dpL = dp.GetLength(1);
        var imax = Min(m, dpL - 1);
        var msum = 0;
        for (int i = 0; i < imax; i++)
        {
            msum += p[i];
            var t = msum - dp[n, i + 1];
            ans = Max(ans, t);
        }
        return ans;
    }
    static int[,] getDP(int[] c, int[] e, int m, int n)
    {
        var mmax = c.Sum();
        var dpmax = Min(mmax, m);
        var dp = new int[n + 1, dpmax + 1];
        for (int i = 0; i < n + 1; i++)
            for (int j = 1; j < dpmax + 1; j++) dp[i, j] = int.MaxValue;
        var jmax = 0;
        for (int i = 1; i <= n; i++)
        {
            jmax += c[i - 1];
            jmax = Min(jmax, dpmax );
            for (int j = 1; j <= jmax; j++)
            {
                var w = dp[i - 1, Max(0, j - c[i - 1])] + e[i - 1];
                dp[i, j] = Min(dp[i - 1, j], w);
            }
        }
        return dp;
    }
}



Measured memory_bytes: 35328
import itertools
n = int(input())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
permutation_list = list(itertools.permutations(p, n))
sort_lst = sorted(permutation_list)
x = tuple(p)
y = tuple(q)
a = sort_lst.index(x)
b = sort_lst.index(y)
print(abs((a+1)-(b+1)))

Measured memory_bytes: 8308
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <random>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

int main() {
    i64 n;
    cin >> n;
    for (i64 i = 0; i <= 100; i += 7) {
        for (i64 j = 0; j <= 100; j += 4) {
            if (i + j == n) {
                cout << "Yes\n";
                return 0;
            }
        }
    }
    cout << "No\n";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define REP(i,x,n) for(int i = (x); i < (n); ++i)
#define ll long long
#define P pair<ll,ll>
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()

const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1);

int main(void)
{
    ll n, x, ans;
    cin >> n >> x;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    ans = abs(x-a[0]);
    REP(i,1,n){
        ans = __gcd(ans, abs(x-a[i]));
    }
    cout << ans << endl;
    return 0;
}

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


using namespace std;

typedef long long ll;

#define pi 2*acos(0.0)


int main(void)
{
    //ios_base::sync_with_stdio(false);
    //cin.tie(0);
    // cout.tie(0);
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++)
    {
        cout<<'x';
    }
    cout<<endl;

}


Measured memory_bytes: 3612
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define ff first
#define ss second

int n;
int mat[22][22];
const int mod=1e9+7;
int memo[22][1<<22];


int dp(int pos, int mask)
{
    if(pos==n)
    {
        if((mask+1)==(1LL<<n))
            return 1;
        return 0;
    }
    int &ans=memo[pos][mask];
    if(ans!=-1)
        return ans;
    ans=0;
    for(int i=0; i<n; i++)
        if((!(mask&(1LL<<i))) and mat[pos][i]==1)
        {
            ans+=dp(pos+1, mask|(1LL<<i));
            ans%=mod;
        }
    return ans;
}

void solve()
{
    cin>>n;
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
            cin>>mat[i][j];
    memset(memo, -1, sizeof(memo));
    cout<<dp(0, 0);
}

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

Measured memory_bytes: 721152
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		long[] q = new long[a];
		long[] p = new long[a];
		long count = 0;
		long sum = 0;
		long h = 0;
		ArrayList<Long> list=new ArrayList<Long>();
		long o = 0;
		long s = 0;
		for(int i = 0; i < a ; i++){
			long c = sc.nextLong();
			q[i]=c;
			o+=c;
		}
		for(int i = 0;i < a ; i++){
			long b = sc.nextLong();
			p[i]=b;
			s+=b;
		}
		if(o>=s){
			for(int i = 0; i<a; i++){
				if(q[i]>=p[i]){
					if(q[i]-p[i]<=o-s){
						list.add(q[i]-p[i]);
					}
					h++;
				}
			}
			if(h==a){
				System.out.println(0);
				return;
			}
		}else{
			System.out.println(-1);
			return;
		}
		Collections.sort(list);
		for(long k: list){
			if(k+sum<=o-s){
				sum+=k;
				count++;
			}
		}
		System.out.println(a-count);
	}
}

Measured memory_bytes: 88932
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin>>s;
  int j,k,l,m,n,su=0;
  j=s.size();
  for(int i=0;i<j;i++){
    m=s[i]-48;
    su=su+m;
  }
  if(su%9==0)
    cout<<"Yes";
  else
    cout<<"No";
}


Measured memory_bytes: 3752
#include <iostream>
#include <string>

using namespace std;

int main(void) {
  long i, ans, tmp;
  long A, B;
  cin >> A >> B;
  // でかいほうをセット
  if(A > B) {
    tmp = A;
  } else {
    tmp = B;
  }
  // 確かめていく
  ans = tmp;
  while( (ans%A != 0) || (ans%B != 0) ) {
    ans += tmp;
  }
  
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
S = input()
K = int(input())

sumarr = list()
cnt = 1
for i in range(1, len(S)):
    if S[i] == S[i - 1]:
        cnt += 1
    else:
        sumarr.append(cnt)
        cnt = 1
sumarr.append(cnt)

if len(sumarr) == 1:
    print(int(len(S) * K / 2))
    exit(0)


def to_cnt(num):
    if num < 2:
        return 0
    else:
        return int(num / 2)


ans = 0
if S[0] == S[len(S) - 1]:
    ans += to_cnt(sumarr[0])
    ans += to_cnt(sumarr[len(sumarr) - 1])
    connection = to_cnt(sumarr[0] + sumarr[len(sumarr) - 1])
    cnt = sum(map(to_cnt, sumarr[1: len(sumarr) - 1]))
    ans += cnt * K
    ans += connection * (K - 1)
else:
    ans += sum(map(to_cnt, sumarr)) * K

print(ans)


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

const int maxn=1e6+5;
int flag[maxn];

signed main()
{
    ios_base::sync_with_stdio(false);
      cin.tie(NULL);
    
    int count;
    cin>>count;
    string nish;
    cin>>nish;
    vector<int>all[2];
    for(int i=0;i<count;i++)
    {
      if(nish[i]=='W')
        all[0].push_back(i);
      else
        all[1].push_back(i);
    }

    reverse(all[1].begin(),all[1].end());
    int siz=all[0].size();
    int siz1=all[1].size();
    int i=0,j=0;
    int count1=0;
    while(i<siz  && j<siz1 )
    {
       if(all[0][i]<all[1][j])
       {
          count1++;
          i++;
          j++;
       }
       else
       {
        break;
       }
    }

    cout<<count1<<endl;

   return 0;

   
}

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

using namespace std;

typedef long long LL;

const LL mod=1000000007;
LL n,m;

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

struct mat{
	LL w[4][4];
	mat(){memset(w,0,sizeof w);}
	mat operator * (const mat &p) const{
		mat ret;
		for (LL k=0;k<4;++k)
			for (LL i=0;i<4;++i)
				for (LL j=0;j<4;++j) upd(ret.w[i][j],w[i][k]*p.w[k][j]);
		return ret;
	}
	mat E(){
		mat ret;
		for (LL i=0;i<4;++i) ++ret.w[i][i];
		return ret;
	}
}ans,b1,b2;

mat pw(mat x,LL k){
	if (!k) return mat().E();
	mat tmp=pw(x*x,k>>1);
	return k&1?tmp*x:tmp;
}

int main(){
	scanf("%lld%lld",&n,&m);
	for (LL i=0;i<4;++i){
		++b1.w[i][0];
		for (LL j=0;j<4;++j)
			if ((i|j)==j){++b1.w[i][j]; ++b2.w[i][j];}
	}
	LL k=1;
	ans=mat().E();
	for (LL i=1;i<=m;++i){
		LL x; scanf("%lld",&x);
		ans=ans*pw(b1,x-k)*b2;
		k=x+1;
	}
	ans=ans*pw(b1,n-k+1);
	printf("%lld\n",ans.w[0][3]);
	
	return 0;
}
			

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e10;
const int MOD = 1e9 + 7;
#define dump(x) cout << #x << " = " << (x) << endl;
#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 all(v) (v).begin(), (v).end()
#define SZ(x) ((int)(x).size())
#define P pair<int, int>
#define V vector<int>
#define M map<int, int>
#define S set<int>
#define itn int
#define tin int
#define tni int
bool dbg = false;
void solve()
{
}

signed main()
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int A, B;
    cin >> A >> B;
    int ans = 0;
    int t = 1;
    while (t < B) {
        ans++;
        t += A - 1;
    }
    cout << ans << endl;
    solve();
    return 0;
}


Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string.h>
#define s(n)                        scanf("%d",&n)
#define sc(n)                       scanf("%c",&n)
#define sl(n)                       scanf("%I64d",&n)
#define sf(n)                       scanf("%lf",&n)
#define ss(n)                       scanf("%s",n)
#define INF                         (int)1e9
#define EPS                         1e-9
#define bitcount                    __builtin_popcount
#define gcd                         __gcd
#define forall(i,a,b)               for(int i=a;i<b;i++)
#define foreach(v, c)               for( typeof( (c).begin()) v = (c).begin();  v != (c).end(); ++v)
#define all(a)                      a.begin(), a.end()
#define in(a,b)                     ( (b).find(a) != (b).end())
#define pb                          push_back
#define fill(a,v)                    memset(a, v, sizeof a)
#define sz(a)                       ((int)(a.size()))
#define mp                          make_pair
#define MOD                         1000000007
typedef long long ll;
/*For you see , each day i love you
 more.Today more than yesterday
  less than tomorrow.*/
using namespace std;

int main()
{
	int n;s(n);
	map<string , int> m;
	int count = 0;
	for(int i = 0;i<n;i++)
	{
		string str;cin>>str;
		if(m[str] == 0) count++;
		m[str] = 1;
	}
	cout<<count<<endl;
	return 0;
}

Measured memory_bytes: 19216
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <functional>
#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <stack>
#include <string>
#include <vector>
 
using namespace std;
typedef long long ll;
using gra = vector<vector<ll>>;
using gram = vector<unordered_map<ll,ll>>;
 
typedef unsigned long long ull;
 
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; }
 
template <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template <class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template <class T> T dup(T a, T b) { return (a + b - 1) / b; }
template <class T> T modpow(T x, T p, T m) { T a=1; while(p){ if(p%2)a =a*x%m; x = x+x%m; p/=2; } return a; }
// template <class T> void prim(T a) { for(ll i=0;i<a.size();++i) { cout << a[i]; } cout << "\n"; }
 
#define mod 1000000007LL
#define INF 10000000000000000LL
 
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define rep1(i, n) for (ll i = 1; i <= n; ++i)
#define rrep(i, n) for (int i = (n - 1); i >= 0; --i)
#define rrep1(i, n) for (int i = n; i > 0; --i)
 
#define pri(x) cout << (x) << "\n"
#define pri2(x, y) cout << (x) << " " << (y) << "\n"
#define pri3(x, y, z) cout << (x) << " " << (y) << " " << (z) << "\n"
//#define modpow(x, p, m) { ll a=1; while(p){ if(p%2)a =a*x%m; x = x+x%m; p/=2; } return a; }
 
#define m0(h) memset(h, 0, sizeof(h))
#define m1(h) memset(h, 1, sizeof(h))
#define m(h, n) memset(h, (n), sizeof(h))
#define all(n) (n).begin(),(n).end()
#define bit(n) (1LL << (n))
#define pb push_back
 
//#ifdef LOCAL
//
//#define dpri(...) fprintf(stderr, __VA_ARGS__)
//#define pria(g) rep(i,g.size()){ cout << i << "{"; rep(j,g[i].size()) cout << g[i][j] << " "; cout << "}" << "\n"; }
//#else
//#define dpri(...) 42
//#define pria(g) 42
//#endif
 
 
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  // ---------------------
  // コーディング開始
  // ---------------------
  ll n;
  string a;
  set<string> aa;
  char tail ;
  cin >> n;
  rep(i,n){
    cin >> a;
    aa.insert(a);
    if(i!=0){
      if(tail!=a[0]){
        pri("No");
        return 0;
      }
    }
    tail = a[a.length()-1];
  }
  if(aa.size()!=n) pri("No");
  else pri("Yes");

  return 0;
}


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

using namespace std;

using ll = long long;
using dd = double;
using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<dd>;
using vb = vector<bool>;

template <class T, class V>
istream& operator>>(istream& in, pair<T, V>& pair) {
    return in >> pair.first >> pair.second;
}

template <class T>
istream& operator>>(istream& in, vector<T>& elements) {
    for (size_t i = 0; i < elements.size(); ++i) {
        in >> elements[i];
    }
    return in;
}

template <class Container, class Element>
bool Contains(const Container& container, const Element& element) {
    return container.find(element) != container.end();
}

template <class T>
ostream& operator<<(ostream& out, const vector<T>& elements) {
    for (const T& element : elements) {
        out << element << ' ';
    }
    return out;
}

template <class T, class V>
ostream& operator<<(ostream& out, const pair<T, V>& pair) {
    out << pair.first << ' ' << pair.second;
}

#define FOR(i,n) for(size_t i=0, i##_len=(n); i<i##_len; ++i)
#define SORT(c) sort((c).begin(), (c).end())

int main() {
    ios_base::sync_with_stdio(false);
    
    int n;
    cin >> n;
    
    vi p(n);
    cin >> p;
    
    int result = 0;
    for (int i = 1; i < n - 1; ++i) {
        result += (p[i] > min(p[i - 1], p[i + 1]) && p[i] < max(p[i - 1], p[i + 1]));
    }
    cout << result << endl;
    
    return 0;
}


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

ll powmod(ll a, ll k, ll m) {
  if (k == 0) return 1;
  ll t = powmod(a, k / 2, m);
  t = (t * t) % mod;
  if (k % 2 == 1) t = (t * a) % mod;
  return t;
}

int main() {
  int n;
  cin >> n;
  int sum = 0;
  for (int a = 1; a < n; a++) {
    sum += (n - 1) / a;
  }
  cout << sum << endl;
  return 0;
}


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

int main(){

  int n,m;

  while(cin >> n >> m, n, m){

    int a[100000] = {0},b[100000] = {0},c[100000] = {0},d[100000] = {0};
    int x,y,count = 0;

    for(int i=0;i<m;i++){
      cin >> x >> y;

      if(x == 1){
	a[y] = 1;
	b[y] = 1;
      }

      c[i] = x;
      d[i] = y;

    }


    for(int i=0;i<m;i++){
      if(b[c[i]] == 1) a[d[i]] = 1;
      else if(b[d[i]] == 1) a[c[i]] = 1;
    }

    for(int i=2;i<=n;i++){
      if(a[i] == 1) count++;
    } 

    cout << count << endl;
  }
}

Measured memory_bytes: 2728
#include <bits/stdc++.h>
#include<stdio.h>
using namespace std;
#define FOR(i,k,n) for(int i = (k); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) begin(a),end(a)
#define MS(m,v) memset(m,v,sizeof(m))
#define D10  fixed<<setprecision(10)
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> P;
typedef long long ll;
const ll INF = 114514810;
const ll MOD = 1000000007;
const double EPS = 1e-8;
const double PI = acos(-1.0);
struct edge
{
	int from, to, cost;
	bool operator < (const edge& e) const { return cost < e.cost; }
	bool operator >(const edge& e) const { return cost > e.cost; }
};
int dx[] = { -1, 0, 0, 1 }; int dy[] = { 0, -1, 1, 0 };
bool valid(int x, int y, int h, int w) { return (x >= 0 && y >= 0 && x < h&&y < w); }
///*************************************************************************************///
///*************************************************************************************///
///*************************************************************************************///

int V, E;
vector<vector<edge>> es;
bool used[10000];

pair<int, vector<edge>> prim()
{
	memset(used, false, sizeof(used));
	vector<edge> res;
	int sum = 0;

	priority_queue<edge, vector<edge>, greater<edge>> que;
	que.push(edge{ -1, 0, 0 });

	while (!que.empty())
	{
		edge e = que.top(); que.pop();
		if (used[e.to]) continue;
		if (e.from >= 0) res.push_back(e);
		sum += e.cost;
		used[e.to] = true;
		for (edge i : es[e.to])
		{
			if (!used[i.to]) que.push(i);
		}
	}
	return pair<int, vector<edge>>(sum, res);
}

int main()
{
	while (cin >> V >> E, V)
	{
		es.clear();
		es.resize(V);
		REP(i, E)
		{
			int a, b, c;
			cin >> a >> b >> c;
			es[a].push_back(edge{ a, b, c });
			es[b].push_back(edge{ b, a, c });
		}
		cout << prim().first << endl;
	}
}

Measured memory_bytes: 1240
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <utility>
#include <cmath>
#include <stdlib.h> 
#include <stdio.h>
#include <iterator>
#include <chrono>
#include <iomanip>
#include <set>
#include <map>
#include <list>
#include <iterator>
#include <deque>
#include <stack>
#include <queue>
#include <fstream>
#include <limits>
#include <unordered_map>
#include <bitset>
#include <numeric>
#include <sstream>
#include <random>
#include <cassert>

using namespace std;
#define ffor(n) for(int i = 0; i < n; i++)
#define fffor(n) for(int j = 0; j < n; j++)
int INF = 1e9 + 7;

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

	int n;
	cin >> n;
	vector <long long> v(n);
	ffor(n) cin >> v[i];
	vector <long long> sum_right(n);
	for (int i = n - 2; i >= 0; i--) {
		sum_right[i] = sum_right[i + 1] + v[i + 1];
		sum_right[i] %= INF;
	}
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		ans += (v[i] * sum_right[i]);
		ans %= INF;
	}
	cout << ans;

}
	




/*
C:\Users\User\Desktop\comp_programming\final_straw_after_this_im_switching_to_vs_code\final_straw_after_this_im_switching_to_vs_code.cpp
*/

Measured memory_bytes: 6344
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef unsigned long long ull;
typedef pair<int,ull> P;
typedef pair<int,int>Pii;
#define F first
#define S second
 
 
int dep=0;;
int X[]={0,3,2,1,0,3,2,1,0,3,2,1,0,3,2,1};
int Y[]={0,3,3,3,3,2,2,2,2,1,1,1,1,0,0,0};
int dy[]={1,0,-1,0};
int dx[]={0,-1,0,1};
ull mask[3][3],bit[3][3];

const int MAX = 333333;
ull G=4886718336 , x , s , M=((ull)1<<(4*9))-1;

Pii pos(ull A){
    r(y,3)r(x,3){
        if(!((A>>bit[y][x])&15)){
            return Pii(y,x);
        }
    }

}

int cost(ull A,int y2,int x2){
	int sum=0;
	r(y,3){
        r(x,3){
            int k=((A>>bit[y][x])&15);
            int t = abs(X[k]-x) + abs(Y[k]-y);
    		sum += t ;
        }
	}
	return sum;
}


signed main(){

    ull init = 0;
    unordered_set<ull>st;

    for(int i=2;i>=0;i--){
        for(int j=2;j>=0;j--){
            ull x;
            cin>>x;
            init|=(x<<((i*3+j)*4));
            mask[i][j] = (ull)15<<((i*3+j)*4);
            bit[i][j] = (i*3+j)*4;
        }
    }



    priority_queue<P> Q[2];
    Q[0].push(P(0,init));
    st.insert(init);
 
    while( !Q[dep%2].empty() ){
        while( !Q[dep%2].empty() ){
            P A=Q[dep%2].top(); Q[dep%2].pop();

            if(A.S==G){
                cout<<dep<<endl;
                return 0;
            }

            Pii p=pos(A.S);
            int x=p.S, y=p.F;
            ull a = (A.S>>bit[y][x])&15;

            r(i,4){
            	int ny=p.F+dy[i];
            	int nx=p.S+dx[i];
            	if( ny<0 || nx<0 || 3<=ny || 3<=nx ) continue;

                ull b = ( A.S>>bit[ny][nx] )&15;
                ull c = ( A.S & ( M - mask[y][x] - mask[ny][nx] ) );
                ull nex = (c | ( b<<bit[y][x] ) | ( a<<bit[ny][nx] ) );

                if(st.count(nex)) continue;
                st.insert(nex);


                Q[(dep+1)%2].push(P(cost(nex,y,x),nex));
                if(Q[(dep+1)%2].size()>=MAX) Q[(dep+1)%2].pop();

            }
        }
        if(dep>=90)break;
        //cout<<(Q[(dep+1)%2].size())<<endl;
        dep++;
    }
    
}


Measured memory_bytes: 11200
#include<stdio.h>

int main(void){
  long long int N,A,B;
  long long int i;
  long long int h[100000];
  long long int K;
  long long int left,right;
  long long int sum;

  scanf("%lld %lld %lld",&N,&A,&B);
  //printf("%d\n", N);

  for(i=0;i<N;++i){
    scanf("%lld",&h[i]);
  }

  left=0;
  right=1000000000;

  while(left!=right-1){
    K=(right+left)/2;
    sum=0;
    for(i=0;i<N;i++){
      if(h[i]-K*B > 0){
        // sum += (h[i]-K*B)%(A-B) ? (h[i]-B*K)/(A-B)+1 : (h[i]-B*K)/(A-B);
        if((h[i]-K*B)%(A-B)==0){
          sum += (h[i]-B*K)/(A-B);
        }else{
          sum += (h[i]-B*K)/(A-B)+1;
        }
      }
    }
    if(sum <= K){
      right=K;
    }else{
      left=K;
    }
  }

  printf("%lld\n", right);

  return 0;
}


Measured memory_bytes: 896
//#define NDEBUG

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define iceil(a, b) ((a + b - 1) / b)
#define tomax(a, b) (a = max(a, b))
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

//#define TEST

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

int main(){
    StarBurstStream

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

    map<pii, int> s;
    map<int, int> rcnt, ccnt;
    for(int i = 0; i < m; i++){
        int x, y;
        cin >> x >> y;
        s[mp(x, y)]++;
        rcnt[x]++; ccnt[y]++;
    }

    int rmx = 0, cmx = 0;
    for(auto i : rcnt) rmx = max(rmx, i.S);
    for(auto i : ccnt) cmx = max(cmx, i.S);

    vector<int> r, c;
    for(auto i : rcnt){
        if(i.S == rmx) r.eb(i.F);
    }
    for(auto i : ccnt){
        if(i.S == cmx) c.eb(i.F);
    }
//    printv(r, cerr);
//    printv(c, cerr);

    int ans = rmx + cmx - 1;
    for(int i : r){
        for(int j : c){
            if(s[mp(i, j)]) continue;
            ans = rmx + cmx;
            goto out;
        }
    }
    out:;

    cout << ans << "\n";

    return 0;
}

Measured memory_bytes: 54228
import Control.Applicative

main :: IO ()
main = solve <$> f >>= putStrLn
  where
    f = map read <$> words <$> getLine

solve :: [Int] -> String
solve [a1, a2, a3]
  | a1 + a2 + a3 < 22 = "win"
  | otherwise = "bust"


Measured memory_bytes: 508
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
//priority_queue<int,vector<int>, greater<int> > q2;



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

	VI N(12);
	REP(i, 12)cin >> N[i];
	SORT(N);
	if (N[0] == N[1] && N[0] == N[2] && N[0] == N[3]) {
		if (N[4] == N[5] && N[4] == N[6] && N[4] == N[7]) {
			if (N[8] == N[9] && N[8] == N[10] && N[9] == N[11]) {
				cout << "yes" << endl;
				return 0;
			}
		}
	}
	cout << "no" << endl;

	return 0;
}




Measured memory_bytes: 3228
#include<bits/stdc++.h>
using namespace std;
#define w(t) int t;cin>>t;while(t--)
#define pb   push_back
#define mk   make_pair
typedef long long ll;
const ll mod=1e9+7;
int dp[1000000];
vector<int>graph[1000000];

int solve(int src){
	if(dp[src]!=-1)return dp[src];
	bool leaf=true;
	int bestChild=0;
	for(int child:graph[src]){
		leaf=0;
		bestChild=max(bestChild,solve(child));
	}
	return dp[src]= leaf ? 0:1+bestChild;
}


int main()
{

	ios_base::sync_with_stdio(false); 
	cin.tie(nullptr); 
	cout.tie(nullptr);
    int n,m;
    cin>>n>>m;
    memset(dp,-1,sizeof dp);
    for(int i=0;i<m;i++){
         int u,v;
         cin>>u>>v;
         graph[u].push_back(v);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
    	ans=max(ans,solve(i));
    }
    cout<<ans;
    return 0;
  
}


/*
so the logic here if this
suppose if my src 1
and
this are path from 1
 1->2->3->4
 then my dp[src]=1+maximum path given by child of 1

 if 1 does not have any child means it is a leaf node then
 there will be no path so my answer will be zero

I will do this for all the node

*/

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

using namespace std;

typedef long long lli;
typedef double lld;
typedef vector<lli> vll;
typedef vector<bool> vbl;
typedef vector<double> vdl;
typedef vector<vector<lli>> mat;
typedef vector<vdl> mad;
typedef unordered_map<lli,unordered_map<lli,lli>> graph;
typedef complex<double> cmp;
typedef vector<cmp> vcl;

const lli e5 = 1 << 20;
const lli mod = 1000000007;
const lli e3 = 1 << 13;
const lli INF = 1ll << 62;

lli h,w;
string a[e3];
graph g;
graph r;
lli idx_w[e5];
lli idx_h[e5];
lli s,t;
lli vis[e5];
lli level[e5];
lli ans = 0;

void bfs(){
  queue<vll> q;
  q.push(vll({s,0}));
  vis[s]++;
  while(!q.empty()){
    vll p = q.front();
    q.pop();
    lli x = p[0];
    lli l = p[1];
    level[x] = l;
    for(auto y : g[x]){
      if(vis[y.first] == 1) continue;
      if(y.second == 0) continue;
      vis[y.first]++;
      q.push(vll({y.first,l+1}));
    }
    for(auto y : r[x]){
      if(vis[y.first] == 1) continue;
      if(y.second == 0) continue;
      vis[y.first]++;
      q.push(vll({y.first,l+1}));
    }

  }
}

lli dfs(lli x,lli c){
  vis[x]++;
  if(x == t) return c;
  for(auto y : g[x]){
    if(vis[y.first] == 1) continue;
    if(y.second == 0) continue;
    if(level[y.first] <= level[x]) continue;
    lli z = dfs(y.first, min(c,y.second));
    if(z > 0){
      g[x][y.first] -= z;
      r[y.first][x] += z;
      return z;
    }
  }
  for(auto y : r[x]){
    if(vis[y.first] == 1) continue;
    if(y.second == 0) continue;
    if(level[y.first] <= level[x]) continue;
    lli z = dfs(y.first, min(c,y.second));
    if(z > 0){
      r[x][y.first] -= z;
      g[y.first][x] += z;
      return z;
    }
  }
  return 0;
}

int main(){
  cin >> h >> w;
  for(lli i = 0;i < h;i++) cin >> a[i];
  lli idx = 1;
  for(lli i = 0;i < w;i++){
    idx_w[i] = idx;
    idx++;
  }
  for(lli i = 0;i < h;i++){
    idx_h[i] = idx;
    idx++;
  }
  s = 0;
  t = idx;
  for(lli i = 0;i < h;i++){
    for(lli j = 0;j < w;j++){
      if(a[i][j] != 'o') continue;
      g[idx_h[i]][idx_w[j]] = 1;
      r[idx_w[j]][idx_h[i]] = 0;
      g[idx_w[j]][idx_h[i]] = 1;
      r[idx_h[i]][idx_w[j]] = 0;
    }
  }
  lli mem_x,mem_y;
  for(lli i = 0;i < h;i++){
    for(lli j = 0;j < w;j++){
      if(a[i][j] != 'S') continue;
      mem_x = j;
      mem_y = i;
      g[s][idx_w[j]] = e5;
      r[idx_w[j]][s] = 0;
      g[s][idx_h[i]] = e5;
      r[idx_h[i]][s] = 0;
    }
  }
  for(lli i = 0;i < h;i++){
    for(lli j = 0;j < w;j++){
      if(a[i][j] != 'T') continue;
      if(i == mem_y || j == mem_x){
        cout << -1 << endl;
        return 0;
      }
      g[idx_w[j]][t] = e5;
      r[t][idx_w[j]] = 0;
      g[idx_h[i]][t] = e5;
      r[t][idx_h[i]] = 0;
    }
  }
  for(;;){
    fill(vis,vis+(idx+1),0ll);
    fill(level,level+(idx+1),-1ll);
    bfs();
    // for(lli i = 0;i <= t;i++) cerr << level[i] << " ";
    // cerr << endl;
    if(level[t] < 0) break;
    for(;;){
      fill(vis,vis+(idx+1),0ll);
      lli z = dfs(s, INF);
      // cerr << " " << z << endl;
      if(z <= 0) break;
      ans += z;
    }

  }
  cout << ans << endl;
}


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

void swap(ll* a, ll* b){
  ll tmp = *a;
  *a = *b;
  *b = tmp;
}

int main(){
  ll N, X;
  cin >> N >> X;
  ll ans = N;

  ll a = X;
  ll b = N-X; // a > b;

  if(a < b) swap(&a, &b);


  //cout << ans << " " << a << " " << b << "\n";
  while(b){
    ll q = a/b;
    ll r = a%b;

    ans += (q*2*b);
    if(r == 0) ans -= b;
    a = b;
    b = r;
    //cout << ans << " " << a << " " << b << "\n";
  }
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 256
#include<cstdio>

int is_odd(int u){
    if(u<=9) return 1;
    else if(u<=99) return 0;
    else if(u<=999) return 1;
    else if(u<=9999) return 0;
    else if(u<=99999) return 1;
    else return 0;
}

int main(){
    int n;
    scanf("%d",&n);
    int ans = 0;
    for(int i = 1; i <= n; i++){
        ans += is_odd(i);
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 128
using System;

public class WaitingHoliday{
    public static void Main(string[] argc){
        string input = Console.ReadLine();
        int remainDays = HowManyDaysToNextHoliday(input);
        Console.WriteLine(remainDays);
    }

    public static int HowManyDaysToNextHoliday(string inputStr) {
        switch(inputStr){
            case "SUN":
            return 7;
            break;
            case "MON":
            return 6;
            break;  
            case "TUE":
            return 5;
            break;  
            case "WED":
            return 4;
            break;  
            case "THU":
            return 3;
            break;  
            case "FRI":
            return 2;
            break;  
            case "SAT":
            return 1;
            break;  
            default:
            return 0;
        }
    }
}

Measured memory_bytes: 13152
#include <stdio.h>

using namespace std;

int main(){
	int r,c,sum,total_sum = 0;
	scanf("%d %d",&r,&c);
	int table[r+1][c+1];

	for(int i = 0; i < r+1; i++){
		for(int j = 0; j < c+1; j++){
			table[i][j] = 0;
		}
	}

	for(int i = 0; i < r; i++){
		sum = 0;
		for(int j = 0; j < c; j++){
			scanf("%d",&table[i][j]);
			sum += table[i][j];
			table[r][j] += table[i][j];
		}
		table[i][c] = sum;
		total_sum += sum;
	}
	table[r][c] = total_sum;

	for(int i = 0; i < r+1; i++){
		for(int j = 0; j < c; j++){
			printf("%d ",table[i][j]);
		}
		printf("%d\n",table[i][c]);
	}
}





Measured memory_bytes: 2780
/*
AUTHOR: Aman Raj
LANG: C++
*/

using namespace std;

typedef   long long  int ll;
#include <bits/stdc++.h>


//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
#define fast  ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
#define all(a) a.begin(),a.end()
//#define mod 998244353


#define mod   1000000007

#define inf 1e18
//#define mod 3
#define flush fflush(stdout)

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef cc_hash_table<ll, ll, hash< ll > > ht;

// find_by_order()  // order_of_key
typedef tree<
    ll,
    null_type,
    less<ll>,
    rb_tree_tag,
    tree_order_statistics_node_update>
    ordered_set;






ll power1(ll a, ll b)//a raised to power b
   {  if(b<=0) return 1; if(b==1) return a;
       ll c=power1(a,b/2);
        c*=c;c%=mod;if(b%2==1) c*=a;c%=mod;
        return c;
   }
   ll mi(ll a,ll m)
   { ll c= power1(a,m-2);

     return c;
   }



 struct less_then_greater {
    template<typename T, typename U>
    bool operator()(T const& lhs, U const& rhs) const {
        if (lhs.first < rhs.first) return true;
        if (rhs.first < lhs.first) return false;
        return lhs.second > rhs.second;
    }
};

 /*std::priority_queue<std::pair<int, int>,
                    std::vector<std::pair<int, int>>,
                    less_then_greater
                    > pq;*/


  int main()
{  fast;
   ll n,k;cin>>n>>k;
    vector<ll> v(n);for(auto &x:v){cin>>x;--x;}
    map<ll,ll> mpp;
    ll ans=0;ll sum=0;
    mpp[0]=1;
    vector<ll> dp(n+1);
    for(ll i=1;i<=n;i++)
    {  if(i>=k)
        {   //if(i==5)cout<<dp[i-k]<<" "<<mpp[dp[i-k]]<<endl;
            mpp[dp[i-k]]--;
        }
       
        sum+=v[i-1];sum%=k;
        ans+=mpp[sum];
        mpp[sum]++;
        dp[i]=sum;
     //cout<<i<<" "<<ans<<endl;

    }


    cout<<ans<<endl;
   return 0;
}


Measured memory_bytes: 18760
def INT():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(map(int, input().split()))

def factrize(P):
    fac = {}
    
    for i in range(2, int(P**0.5) + 1):
        e = 0
        while P % i == 0:
            P //= i
            e += 1
            
        if e > 0:
            fac[i] = e
    
    if P > 1:
        fac[P] = 1
    
    return fac

N, P = MI()
ans = 1

for f, e in factrize(P).items():
    if e >= N:
        ans *= f**(e // N)
        
print(ans)

Measured memory_bytes: 63392
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

N = int(input())
As = []
Bs = []
for n in range(N):
    a, b = map(int, input().split())
    As.append(a)
    Bs.append(b)

As.reverse()
Bs.reverse()
offset = 0
for a, b in zip(As, Bs):
    a += offset
    if a % b != 0:
        offset += b - (a % b)
print(offset)        



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

using namespace std;

using int64 = long long;

int N, T[200], V[200];

int t;
int f[40001];
bool memo[40001][201];
double dp[40001][201];

double rec(int idx, double v)
{
  if(v < 0) return (-1e20);
  if(v > f[idx]) return (-1e20);
  if(idx == t) return (0.0);
  if(memo[idx][(int) (v * 2)]++) return (dp[idx][(int) (v * 2)]);
  double ret = -1e20;
  ret = max(ret, rec(idx + 1, v) + v * 0.5);
  ret = max(ret, rec(idx + 1, v + 0.5) + v * 0.5 + 0.5 * 0.5 / 2);
  ret = max(ret, rec(idx + 1, v - 0.5) + v * 0.5 - 0.5 * 0.5 / 2);
  return (dp[idx][(int) (v * 2)] = ret);
}

int main()
{
  cin >> N;
  for(int i = 0; i < N; i++) cin >> T[i];
  for(int i = 0; i < N; i++) cin >> V[i];

  t = 1;
  for(int i = 0; i < N; i++) {
    f[t - 1] = min(f[t - 1], V[i]);
    for(int j = 1; j <= 2 * T[i]; j++) f[t++] = V[i];
  }
  --t;
  f[t] = 0;
  cout << fixed << setprecision(10) << rec(0, 0) << endl;
}

Measured memory_bytes: 73600
#include <iostream>
using namespace std;
int main(void){
    int A,B,C,D,E,F;
    cin>>A>>B>>C>>D>>E>>F;
    for(int i=0;i<30;i++){
        if(A<B){swap(A,B);}
        if(B<C){swap(B,C);}
        if(C<D){swap(C,D);}
        if(E<F){swap(E,F);} 
    }cout<<A+B+C+E<<endl;
}


Measured memory_bytes: 3084
#include<bits/stdc++.h>
using namespace std;
int a,b,c,x[4][4];
int main()
{
	scanf("%d%d%d",&a,&b,&c);
	x[1][1]=a;
	x[1][2]=b;
	x[2][2]=c;
	for (int i=1;i<=1000;i++)
	{
		x[1][3]=i-x[1][1]-x[1][2];
		x[3][2]=i-x[1][2]-x[2][2];
		x[3][1]=i-x[1][3]-x[2][2];
		x[2][1]=i-x[1][1]-x[3][1];
		x[2][3]=i-x[2][1]-x[2][2];
		x[3][3]=i-x[1][3]-x[2][3];
		if (x[1][1]+x[1][2]+x[1][3]==i&&x[2][1]+x[2][2]+x[2][3]==i&&x[3][1]+x[3][2]+x[3][3]==i&&x[1][1]+x[2][1]+x[3][1]==i&&x[1][2]+x[2][2]+x[3][2]==i&&x[1][3]+x[2][3]+x[3][3]==i&&x[1][1]+x[2][2]+x[3][3]==i&&x[1][3]+x[2][2]+x[3][1]==i)
		{
			for (int j=1;j<=3;j++)
			{
			  for (int k=1;k<=3;k++)
              printf("%d ",x[j][k]);
              printf("\n");
            }
            break;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main(){

  int n,y;

  cin >> n >> y;

  int i,j;
  int ans[3];
  fill(ans,ans+3,-1);
  for(i=min(n,y/10000);i>=0;i--){
    if(ans[0] != -1 && ans[1] != -1 && ans[2] != -1) break;
    for(j=min(n-i,(y-10000*i)/5000);j>=0;j--){
      if(y == 10000*i + 5000*j + 1000*(n-i-j)){
        ans[0] = i;
        ans[1] = j;
        ans[2] = n-i-j;
        break;
      }
    }
  }
  for(i=0;i<3;i++){
    cout << ans[i] << " ";
  }
  cout << endl;


  return 0;

}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cctype>
 
int
main(void)
{
  int a, b;
  std::string s;
  std::cin >> a >> b >> s;
  int start = 0;
  int end = a;
  for (int i = start; i < end; ++i) {
    if (! isdigit(s[i])) {
      std::cout << "No" << std::endl;
      return 0;
    }
  }
  start = end;
  if (s[start] != '-') {
    std::cout << "No" << std::endl;
    return 0;
  }
  ++start;
  end = start + b;
  for (int i = start; i < end; ++i) {
    if (! isdigit(s[i])) {
      std::cout << "No" << std::endl;
      return 0;
    }
  }
  std::cout << "Yes" << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<cstdio>
#include<set>
#include<algorithm>
#define ll long long
using namespace std;

int c[100000]{};
int f[100000]{};
int main() {
	int a, b;
	scanf("%d%d", &a, &b);
	for (int d = 0; d < b; d++) {
		int e;
		scanf("%d",&e);
		f[d] = e;
	}
	for (int g = 0; g < b - 1; g++) {
		c[min(f[g], f[g + 1])-1]++;
		c[max(f[g], f[g + 1])-1]--;
	}
	int s = 0;
	ll p = 0;
	for (int h = 0; h < a - 1; h++) {
		s += c[h];
		ll x, y, z;
		cin >> x >> y >> z;
		ll o= min(z + y*s, x*s);
		p += o;
	}
	cout << p << endl;
}

Measured memory_bytes: 3916
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define start_routine() int begtime = clock();
#define end_routine() int endtime = clock(); cerr << endl << "Time elapsed: " << (endtime - begtime)*1000/CLOCKS_PER_SEC << " ms"; return 0
#define speed() cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(false)
// #define exit(a, b) return cout << a, b;

// debugger
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#define debug(stuff) cout << #stuff << ": " << stuff <<endl
#define debugc(stuff) cout << #stuff << ": "; for(auto x: stuff) cout << x << " "; cout << endl;
// 

#define loop(i,a,b) for(ll i=a;i<b;i++)
#define all(v) v.begin(), v.end() 

#define print(stuff) cout << stuff << endl
#define printc(stuff) for(auto x: stuff) cout << x << " "; cout << endl;
#define printPrec(stuff) cout << fixed << setprecision(15) << stuff << endl;
#define len length
#define ret0 return 0
#define ret return 


#define ll long long
#define ld long double
#define fi first
#define endl '\n'
#define se second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fill(ar, x) memset(ar, x, sizeof ar)

#define vl vector<ll> 
#define sl set<ll>
#define pll pair<ll, ll>
#define mll map<ll, ll> 
#define pq priority_queue<ll>

// typedef tree<ll,null_type,less<ll>,rb_tree_tag,
// tree_order_statistics_node_update> indexed_set;

#define inf (long long int) 1e18
#define eps 0.000001
#define mod 1000000007
#define mod1 998244353
#define MAXN (ll)1e5+5

void solve(){
    ll n;
    cin>>n;
    if(n == 1){
        print(0);
    }
    else {
        n--;
        ll x = (n*(n+1))/2;
        print(x);
    }
}

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

    ll t = 1;
    // cin>>t;
    while(t--){
        solve();
    }
        

}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using P = pair<int,int>;
template <class T> void chmin(T &a, const T &b) noexcept { if (b < a) a = b; }
template <class T> void chmax(T &a, const T &b) noexcept { if (a < b) a = b; }
void debug_out() { cout << "\n"; }
template <class T, class... Args>
void debug_out(const T &x, const Args &... args) { cout << x << " "; debug_out(args...);}
#ifdef _DEBUG
  #define debug(...) debug_out(__VA_ARGS__)
#else
  #define debug(...) 
#endif

// const int mod = 1000000007;
const int mod = 998244353;
struct mint {
  ll x;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
  bool operator==(const mint rhs) const { return x == rhs.x; }
  bool operator!=(const mint rhs) const { return x != rhs.x; }
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}


int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  int n, s;
  cin >> n >> s;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  vector<vector<mint> > F(n+5, vector<mint>(s+5,0));
  F[0][0] = 2;
  if (a[0] <= s) F[0][a[0]] = 1;
  for (int i = 1; i < n; ++i) {
    for (int j = 0; j <= s; ++j) {
      F[i][j] += F[i-1][j] * 2;
      if (j+a[i] <= s) F[i][j+a[i]] += F[i-1][j];
    }
  }
  cout << F[n-1][s] << endl;
  return 0;
}

Measured memory_bytes: 73884