akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Linq;

namespace ABC
{
    using System.Collections;
    using System.Collections.Generic;
    using System.Runtime.CompilerServices;
    using System.Runtime.InteropServices;
#if USE_STUB
    using static Stub.Console;
#else
    using static System.Console;
#endif
    using static System.Math;
    public class Program
    {
        static void Main(string[] args)
        {
            foreach (var item in Solve())
            {
                WriteLine(item);
            }
        }

        static IEnumerable<object> Solve()
        {
            var nm = ReadLine().Split().Select(int.Parse).ToArray();
            var n = nm[0];
            var m = nm[1];
            var PYs = new PY[m];
            for (int i = 0; i < m; i++)
            {
                var py = ReadLine().Split().Select(int.Parse).ToArray();
                PYs[i] = new PY(py[0], py[1]);
            }
            var dic = PYs.GroupBy(py => py.P).Select(g => g.OrderBy(py => py.Y).Select((py, i) => new { py, i })).SelectMany(x => x).ToDictionary(x => x.py, x => x.i + 1);

            foreach (var py in PYs)
            {
                var v = dic[py];
                yield return $"{py.P:D6}{v:D6}";
            }
        }
        public struct PY
        {
            public int P { get; }
            public int Y { get; }
            public PY(int p, int y)
            {
                P = p; Y = y;
            }
        }
    }
}


Measured memory_bytes: 34736
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
class Program
{
    static void Main(string[] args)
    {
            // 入力
            string[] sS = System.Console.ReadLine().Trim().Split(' ');
            int iN = int.Parse(sS[0]);
            sS = System.Console.ReadLine().Trim().Split(' ');
            List<int> lstSid = new List<int>();
            for (int i = 0; i < sS.Length; i++)
            {
                lstSid.Add(int.Parse(sS[i]));
            }

            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            sw.Start();

            // 解析
            lstSid.Sort(delegate (int mca1, int mca2) { return mca2 - mca1; });         // 降順
            int iM = lstSid[0];                                                         // 最長別
            lstSid.RemoveAt(0);                                                         // 最長削除
            string sOut = "Yes";
            if (iM >= lstSid.Sum()) { sOut = "No"; }

            // 出力
            System.Console.WriteLine("{0}", sOut.ToString());

            sw.Stop();
#if DEBUG
            Console.WriteLine();
            Console.WriteLine("{0}", sw.Elapsed.ToString());
            Console.WriteLine("続行するには何かキーを押してください．．．");
            Console.ReadKey();
#endif
    }

}


Measured memory_bytes: 13396
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
string s, t, x;
vector<string> v;
int main() {
	int i, j;
	cin>>s>>t;
	if(s.size()<t.size()) {cout<<"UNRESTORABLE"; return 0;}
	for(i=0; i<=s.size()-t.size(); i++) {
		for(j=0; j<t.size(); j++) {
			if(s[i+j]!='?' && s[i+j]!=t[j]) break;
		}
		if(j==t.size()) {
			x = s;
			for(j=0; j<t.size(); j++) x[i+j] = t[j];
			for(j=0; x[j]; j++) if(x[j]=='?') x[j] = 'a';
			v.push_back(x);
		}
	}
	if(v.empty()) cout<<"UNRESTORABLE";
	else {
		sort(v.begin(), v.end());
		cout<<v[0];
	}
	return 0;
}

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

int main()
{
    int N,temp,count=0;
    cin>>N;
    for(int i=0;i<N;++i)
    {
        cin>>temp;
        if((i%2)==0&&(temp%2)==1)
            ++count;
    }
    cout<<count;
    return 0;
}


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

int main () {
    ll n;
    cin>>n;
    ll a[300005],b[300005];
    for(int i=0;i<n;i++){int x;
        cin>>x;
        a[x-1]++;
    }
    sort(a,a+n,greater<int>());
    int j=n-1;
    ll sum=0;
    for(int i=1;i<=n;i++){
        
        while(j>=0 && a[j]<i){
            sum+=a[j];
            j--;
        }
        
        b[i]= sum/i +(j+1);
    }
 
    j=n;
    for(int i=1;i<=n;++i){
        
      while(j>=1 && b[j]<i) {
             
             j--;
             
      }  
        cout<<j<<"\n";
        
    }

}

Measured memory_bytes: 8212
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN=100000;
const int MOD=1000000007;
void inc(int &a,int b) { if((a+=b)>=MOD) a-=MOD; }

int n;
vector<int> adj[MAXN];

pair<int,int> dfs(int at,int par) { // black,white
	pair<int,int> ret=MP(1,1);
	REPSZ(i,adj[at]) {
		int to=adj[at][i]; if(to==par) continue;
		pair<int,int> cur=dfs(to,at);
		ret.first=(ll)ret.first*cur.second%MOD;
		ret.second=(ll)ret.second*(cur.first+cur.second)%MOD;
	}
	return ret;
}

int solve() {
	pair<int,int> res=dfs(0,-1);
	return (res.first+res.second)%MOD;
}

void run() {
	scanf("%d",&n);
	REP(i,n-1) { int a,b; scanf("%d%d",&a,&b); --a,--b; adj[a].PB(b),adj[b].PB(a); }
	printf("%d\n",solve());
}

int main() {
	run();
	return 0;
}


Measured memory_bytes: 12672
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n;
    cin>>n;
    long long v=0,e=0;
    for(int i=1;i<=n;i++)v+=i*(n-i+1);
    long long x[n-1],y[n-1];
    for(int i=0;i<n-1;i++){
        cin>>x[i]>>y[i];
        e+=min(x[i],y[i])*(n-max(x[i],y[i])+1);
    }
    cout<<v-e<<endl;
    return 0;
}


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

#define rep(i,x,y) for(int i=(x);i<(y);++i)
#define debug(x) #x << "=" << (x)

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl
#else
#define print(x)
#endif

const int inf=1e9;
const int64_t inf64=1e18;
const double eps=1e-9;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){
    os << "[";
    for (const auto &v : vec) {
    	os << v << ",";
    }
    os << "]";
    return os;
}

using i64=int64_t;

void solve(){
    i64 N,D;
    cin >> N >> D;
    
    vector<i64> d(N);
    rep(i,0,N) cin >> d[i];

    vector<i64> pos(N+1);
    pos[0]=D;
    rep(i,1,N+1){
        i64 next=abs(pos[i-1]-d[i-1]);
        if(next<pos[i-1]) pos[i]=next;
        else pos[i]=pos[i-1];
    }

    i64 Q;
    cin >> Q;

    vector<vector<i64>> queries(500000);
    rep(i,0,Q){
        i64 q;
        cin >> q;
        queries[q-1].push_back(i);
    }

    vector<bool> ans(Q);
    vector<pair<i64,i64>> curr;
    curr.push_back(make_pair(0,0));


    for(int i=N-1; i>=0; --i){
        if(!queries[i].empty()){
            bool ok=pos[i]>curr.begin()->second;
            rep(j,0,queries[i].size()) ans[queries[i][j]]=ok;
        }

        if(i==0) continue;
        
        vector<pair<i64,i64>> next;
        auto add=[&](i64 l,i64 r){
            if(l>D) return;
            next.push_back(make_pair(l,min(r,D)));
        };
        for(const pair<i64,i64>& in:curr){
            i64 l=in.first,r=in.second;
            add(d[i]+l,d[i]+r);

            if(2*l>d[i]) continue;
            i64 r_=min(r,d[i]/2);
            add(d[i]-r_,d[i]-l);
            add(l,r_);
        }

        sort(next.begin(),next.end());
        curr.clear();

        i64 l=-1,r=-1;
        rep(j,0,next.size()){
            if(l==-1){
                l=next[j].first;
                r=next[j].second;
                continue;
            }
            if(r+1<next[j].first){
                curr.push_back(make_pair(l,r));
                l=next[j].first;
                r=next[j].second;
                continue;
            }
            r=next[j].second;
        }
        curr.push_back(make_pair(l,r));
    }

    rep(i,0,Q) if(ans[i]) cout << "YES" << endl;
    else cout << "NO" << endl;
}

int main(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}


Measured memory_bytes: 37376
#include <stdio.h>
int main(){
	int a,b;
	scanf ("%d%d",&a,&b);
	if(a==1)
	{
		a=14;
	}
	if(b==1)
	{
		b=14;
	}
	if(a==b){
printf("Draw");
	}
	else if(a>b){
	printf("Alice");
		}
		else
		{
	printf("Bob");
		}
	return 0;
	}

Measured memory_bytes: 128
#include <stdio.h>
int main(){
    int a,b,c;
  
    scanf("%d %d %d",&a,&b,&c);
    if(a==b && b!=c){
        printf("Yes");
    }else if(c==b && b!=a){
        printf("Yes");
    }else if(c==a && b!=a){
        printf("Yes");
    }else{
        printf("No");
    }
    
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, x, y) for(int i = x; i <= y; i ++)
#define rrep(i, x, y) for(int i = x; i >= y; i --)
#define ll long long
#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define pii pair<ll, ll>
#define ls rt << 1
#define rs rt << 1 | 1
#define sz(x) (int)(x).size()
#define ALL(x) (x).insgin(), (x).end()
#define vi vector<int>
#define EPS 1e-8
using namespace std;
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
inline ll read1()
{
	ll x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
char c[1005][1005];
int flag = 0;
void dfs(int n, int m, int a, int b)
{
    int i, j;
    if (n % 2 == 1)
    {
        for (i = m % 2; i + 1 < m; i += 2)
        {
            if (a <= 0) break;
            c[n - 1][i] = '<';
            c[n - 1][i + 1] = '>';
            a --;
        }
    }
    if (m % 2 == 1)
    {
        for (i = 0; i + 1 < n; i += 2)
        {
            if (b <= 0) break;
            c[i][m - 1] = '^';
            c[i + 1][m - 1] = 'v';
            b --;
        }
    }
    
    {
        if ((a % 2 == 1) && (b % 2 == 1) && (n % 2 == 1) && (m % 2 == 1) && (n > 1) && (m > 1))
        {
            c[n - 3][0] = '<';
            c[n - 3][1] = '>';
            c[n - 2][0] = '^';
            c[n - 1][0] = 'v';
            a --;
            b --;
        }
        for (i = 0; i + 1 < n; i += 2)
        {
            for (j = 0; j + 1 < m; j += 2)
            {
                if (c[i][j] != '.') continue;
                if (a)
                {
                    c[i][j] = '<';
                    c[i][j + 1 ] ='>';
                    a --;
                    if (a)
                    {
                        c[i + 1][j] = '<';
                        c[i + 1][j + 1] = '>';
                        a --;
                    }
                }
                else
                {
                    if (b)
                    {
                        c[i][j] = '^';
                        c[i + 1][j] = 'v';
                        b --;
                        if (b)
                        {
                            c[i][j + 1] = '^';
                            c[i + 1][j + 1] = 'v';
                            b --;
                        }
                        if (b == 0) return;
                    }
                }
            }
        }
        if ((!a)&&(!b)) return;
        puts("NO");
        flag = -1;
    }
}
int main()
{
    int n,m,a,b;
    scanf("%d%d%d%d", &n, &m, &a, &b);
    memset(c,'.',sizeof(c));
    dfs(n, m, a, b);
    if (flag == -1) return 0;
    puts("YES");
    rep(i, 0, n - 1)
    {
        c[i][m] = '\0';
        printf("%s\n", c[i]);
    }
    return 0;
} 


Measured memory_bytes: 2176
using System;
using System.Linq;
using System.Collections.Generic;
using System.Numerics;
using static System.Console;

class Program {
    internal static void Main(string[] args) {
        var N = int.Parse(ReadLine());

        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 15; j++) {
                int sum = (i * 4) + (j * 7);
                if (sum > 100) { break; }
                if (sum == N) {
                    WriteLine("Yes");
                    return;
                }
            }
        }
        WriteLine("No");
    }
}

Measured memory_bytes: 11092
#include<bits/stdc++.h>
#define lowbit(i) ((i)&(-(i)))
#define lson(i) ((i)<<1)
#define rson(i) ((i)<<1|1)
#define fi first
#define se second
#define m_p(x,y) make_pair((x),(y))
using namespace std;

typedef long long ll;typedef unsigned long long ul;
typedef pair<int,int> pii;typedef pair<ll,ll> pll;
typedef vector<string> vss;
typedef vector<int> vii;typedef vector<pii> vpi;
typedef queue<int> qii;typedef queue<pii> qpi;

const int inf=0x3f3f3f3f;
const int maxn=307;

int n,res;
char c[maxn][maxn];

bool check(int p){
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			if(c[i][j]!=c[(j+p+n)%n][(i-p+n)%n])
				return false;
	return true;
}

int main()
{
// 	freopen("","r",stdin);
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		getchar();
		for(int j=0;j<n;j++)
			c[i][j]=getchar();
	}
	for(int i=-n+1;i<=n-1;i++){
		if(check(i))
			res+=(n-abs(i));
	}
	printf("%d\n",res);
	return 0;
}



Measured memory_bytes: 384
// clang-format off
#include <bits/stdc++.h>

#define mp make_pair
#define fst first
#define snd second
#define forn(i,n) for (int i = 0; i < int(n); i++)
#define forn1(i,n) for (int i = 1; i <= int(n); i++)
#define popcnt __builtin_popcount
#define ffs __builtin_ffs
#define ctz __builtin_ctz
#define clz __builtin_clz
#define all(a) (a).begin(), (a).end()
 
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
using pil = pair<int,ll>;
using pll = pair<ll,ll>;
template <typename T> using vec = vector<T>;
using vi = vec<int>;
using vl = vec<ll>;
template <typename T> using que = queue<T>;
template <typename T> using deq = deque<T>;

template <typename T> T id(T b) {return b;};
template <typename T> void chmax(T &x, T y) {if (x < y) x = y;}
template <typename T> void chmin(T &x, T y) {if (x > y) x = y;}
template <typename S, typename K> bool contains(S &s, K k) { return s.find(k) != s.end(); }
void fastio() { ios_base::sync_with_stdio(false); cin.tie(nullptr); }
constexpr ll TEN(int n) { if (n == 0) return 1LL; else return 10LL*TEN(n-1); }
// clang-format on

int main() {
    fastio();

    int x;
    cin >> x;

    int c1 = x / 500;
    int c2 = (x - 500 * c1) / 5;

    cout << c1 * 1000 + c2 * 5 << endl;

    return 0;
}

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


int main(void){
    
    int N;
    cin >> N;
    long long A[N];
    
    for(int i = 0; i < N ;i++)cin >> A[i];
    
    map<int,long long> sum;
    map<int,long long> Isum;
    sum[0] = A[0];
    //cout << sum[0] <<endl;
    for(int i = 1; i < N ;i++){
        sum[i] += A[i] + sum[i-1];
        //cout << sum[i] <<endl;
    }
    //cout << sum[N-1]-sum[0] <<"-"<< sum[0]<<endl;
    long long ans = abs((sum[N-1]-sum[0])-sum[0]);
    long long calc;
    
    for(int i = 1; i < N-1 ;i++){
        //cout << sum[N-1]-sum[i] <<"-"<< sum[i]<<endl;
        calc = abs((sum[N-1]-sum[i])-sum[i]);
        ans = min(calc,ans);
    }
    cout << ans <<endl;
    
    
    
    
    
    
    
    
    
    
    
    
    
}


Measured memory_bytes: 14336
#include"bits/stdc++.h"
using namespace std;

typedef pair<int,int> P;
int h,w;

bool movecheck(int x, int y){
    if (0<=x && x<w && 0<=y && y<h) return true;
    else return false;
}

int main(){
    cin >> h >> w;
    vector<vector<bool>> a(h,vector<bool>(w));
    char x;
    
    queue<P> que;
    
    for (int i = 0; i<h; i++){
        for (int j = 0; j<w; j++){
            cin >> x;
            if (x=='#'){
                a[i][j]=true;
                que.push({i,j});
            }
            else a[i][j]=false;
        }
    }
    int ans = 0;
    bool flag;
    vector<int> dx = {1,-1,0,0};
    vector<int> dy = {0,0,1,-1};
    
    while(que.size()>0){
        int l = (int)que.size();
        flag = false;
        for (int i = 0; i<l; i++){
            P p = que.front(); que.pop();
            int y = p.first;
            int x = p.second;
            for (int k = 0; k<4; k++){
                int nx = x+dx[k];
                int ny = y+dy[k];
                if (movecheck(nx,ny) && a[ny][nx]==false){
                    a[ny][nx]=true;
                    flag = true;
                    que.push({ny,nx});
                }
            }
        }
        if (flag) ans++;
    }
    cout << ans << endl;
}







Measured memory_bytes: 8592
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd


def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    s=list(input())
    t=set(s)
    if len(t)==2:
        print('Yes')
    else:
        print('No')


if  __name__=='__main__':
    main()


Measured memory_bytes: 5352
#!/usr/bin/env python3
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def main():
    _ = int(readline())
    Bs = list(map(int, readline().split()))
    As = [Bs[0]] + [min(b, b_next) for b, b_next in zip(Bs, Bs[1:])] + [Bs[-1]]
    print(sum(As))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
#define REP(i,a) for (int i = 0;i < (a);++i)
#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 ALL(obj) (obj).begin(),(obj).end()
#define SORT(list) sort(ALL((list)));
#define MOD 1000000007
using namespace std;
using ll = long long;
int main(){
    string s;
    cin >> s;
    REP(i,3){
        if(s[i] == '7'){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const long long mod = 1000000007;
const long long inf = 1e18;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,z,w;
    cin>>n>>z>>w;
    vi v;
    for(int i=0;i<n;i++){
        int k;
        cin>>k;
        v.pb(k);
    }
    if(n==1){
        cout<<abs(v[0]-w)<<endl;
    }
    else{
        cout<<max(abs(v[n-1]-v[n-2]),abs(v[n-1]-w));
    }
    return 0;
}


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

int main()
{
    long N;
    std::string S;
    std::cin >> N;
    std::cin >> S;
    long count=1;
    char color = S[0];
    for(long i=1; i<S.length(); i++){
        if(color!=S[i]){
            count++;
            color=S[i];
        }
    }
    std::cout << count << std::endl;
    return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<set>
#include<iomanip>
#define pi 3.14159265358979323846
#define ll long long
#define rep(i, a, n) for(int i = a; i < n; i++)
using namespace std;
int main(){
  int n, m;
  cin >> n;
  m = n / 15;
  n = n * 800;
  m = m * 200;
  cout << n - m << "\n";
}

Measured memory_bytes: 3556
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>


#define INF 4000000000000000000LL
#define MOD 1000000007
#define ALL(x) std::begin(x), std::end(x)


std::map<long long, int> prime_factors(long long n) {
  std::map<long long, int> map;

  for (long long i = 2; i * i <= n; i ++)
    for ( ; n % i == 0; n /= i)
      map[i] ++;

  if (n != 1)
    map[n] = 1;

  return std::move(map);
}


std::map<std::pair<int, int>, int> memo;


int dfs(int i, int j)
{
  if (i == 0)
    return 0;

  std::pair<int, int> key(i, j);

  if (memo.count(key))
    return memo[key];
    
  int xp = -1;
  
  for (int k = j; k <= i; k ++)
    xp = std::max(dfs(i - k, k + 1) + 1, xp);

  return memo[key] = xp;
}


int main(int argc, char** argv)
{
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);

  std::cout << std::fixed << std::setprecision(6);
  std::cerr << std::fixed << std::setprecision(6);

  long long N;

  std::cin >> N;

  auto primes = prime_factors(N);

  int C = 0;

  std::map<int, int> map;

  for (const auto& kv : primes) {
    if (map.count(kv.second) == 0)
      map[kv.second] = dfs(kv.second, 1);

    C += map[kv.second];
  }

  std::cout << C << std::endl;
  
  return 0;
}


Measured memory_bytes: 3660
#include <iostream>
using namespace std;
int N, M, A, B, C, T, S[55], X[55][55], Y[55][55], Z[55][55];
void mul() {
	int R[55][55];
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int sum = 0;
			for (int k = 0; k < N; k++) sum += X[i][k] * Y[k][j];
			R[i][j] = sum % M;
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) X[i][j] = R[i][j];
	}
}
void power() {
	for (int i = 30; i >= 0; i--) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < N; k++) Y[j][k] = X[j][k];
		}
		mul();
		if (T & (1 << i)) {
			for (int j = 0; j < N; j++) {
				for (int k = 0; k < N; k++) Y[j][k] = Z[j][k];
			}
			mul();
		}
	}
}
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	while (cin >> N >> M >> A >> B >> C >> T, N) {
		for (int i = 0; i < N; i++) cin >> S[i];
		for (int i = 0; i < N; i++) {
			Z[i][i] = B;
			if (i != 0) Z[i][i - 1] = A;
			if (i + 1 != N) Z[i][i + 1] = C;
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) X[i][j] = 0;
			X[i][i] = 1;
		}
		power();
		for (int i = 0; i < N; i++) {
			int ret = 0;
			for (int j = 0; j < N; j++) ret += X[i][j] * S[j];
			if (i) cout << ' ' << ret % M;
			else cout << ret % M;
		}
		cout << endl;
	}
}

Measured memory_bytes: 3220
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  int tc; scanf("%d", &tc);
  for(int tci = 0; tci < tc; tci++) {
    char str[80]; scanf(" %s", str);
    vector<string> strings;
    int N = strlen(str);
    for(int i = 1; i < N; i++) {
      for(int f = 0; f < 8; f++) {
        string s; s.resize(N);
        for(int j = 0; j < N; j++) {
          int k = j;
          if((f&1) && k < i) k = i-1-k;
          if((f&2) && i <= k) k = N+i-1-k;
          if(f&4) k = N-1-k;
          s[k] = str[j];
        }
        strings.push_back(s);
      }
    }
    sort(strings.begin(), strings.end());
    int M = unique(strings.begin(), strings.end())-strings.begin();
    printf("%d\n", M);
  }
  return 0;
}

Measured memory_bytes: 1164
#!usr/bin/env python3
from collections import defaultdict
import math
import bisect
import random
def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return list(input())
def IIR(n): return [II() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
mod = 1000000007

#A
"""
a,b = LI()
if b % a == 0:
    print(a+b)
else:
    print(b-a)
"""

#B
n,m = LI()
lis = [0 for i in range(m)]
for i in range(n):
    k = LI()
    for j in k[1:]:
        lis[j-1] += 1
ans = 0
for i in lis:
    if i == n:ans += 1
print(ans)
#C
"""
def gcd(a,b):
    if a == 0:
        return b
    return gcd(b%a,a)
n = II()
a = LI()
ans = a[0]
for i in range(1,n):
    ans = gcd(ans,a[i])
print(ans)
"""

#D

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T


Measured memory_bytes: 39152
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <string>
using namespace std;
typedef double  dbl;
typedef long long int lld;
#define MAX std::numeric_limits<lld>::max();
#define MIN std::numeric_limits<lld>::min();
#define FastIO  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
lld palm (string s, lld l, lld r){
	while (l <= r){
		if (s[l] != s[r]){
			return 0;
		}
		l+=1; r -= 1;
	}
			return 1;
}
int main (){
    FastIO
    dbl l, i;
    cin >> l;
    cout << fixed << setprecision(12) << (l/3.0) * (l/3.0) * (l/3.0) << "\n";
    return 0;
}

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

int main()
{
    char a[101];
    gets(a);
    int n = strlen(a);
    printf("%c%d%c", *a, n - 2, *(a + n - 1));
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
// #include <iomanip>
// std::cout << std::fixed << std::setprecision(5);

int main()
{
    long long int a, b;
    std::cin >> a >> b;
    long long int t = (a+b) % 2;
    if(t == 0) std::cout << (a+b)/2 << std::endl;
    else std::cout << "IMPOSSIBLE" << std::endl;
    return 0;
}

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

int main() {
    long int n,y;
    cin>>n>>y;

    for(long int i=0;i*10000<=y;i++){
        for(long int j=0;i*10000+j*5000<=y;j++){
            if(i*10000+j*5000+(n-i-j)*1000==y && n-i-j>=0){
                cout<<i<<" "<<j<<" "<<n-i-j<<endl;
                return 0;
            }
        }
    }
    cout<<-1<<" "<<-1<<" "<<-1<<endl;
}

Measured memory_bytes: 256
A, B, K = [int(_) for _ in input().split()]

while 1:
    if K == 0:
        break
    K -= 1
    A, B = A // 2, B + A // 2
    if K == 0:
        break
    K -= 1
    A, B = A + B // 2, B // 2

print(A, B)


Measured memory_bytes: 3060
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const long double EPS=1e-9;
const long double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
long double ABS(long double a){return max(a,-a);}

int main(){
	int a;scanf("%d",&a);
	int ret=1;
	for(int i=2;i<1000;i++){
		int cur=i*i;
		while(cur<=a){
			ret=max(ret,cur);
			cur*=i;

		}
	}
	printf("%d\n",ret);
}

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

int S[100000];

bool binarySearch(int A[], int n, int key)
{
	int left = 0, right = n;
	int mid;
	while (left < right)
	{
		mid = (left + right) / 2;
		if (A[mid] == key) return true;
		else if (A[mid] < key) left = mid + 1;
		else right = mid;
	}
	return false;
}

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> S[i];

	int q, k, cnt = 0;
	cin >> q;
	for (int i = 0; i < q; i++)
	{
		cin >> k;
		if (binarySearch(S, n, k)) cnt++;
	}

	cout << cnt << endl;;

	return 0;
}


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

int main() {
  string s, ans = "";
  cin >> s;
  for (auto c : s) {
    if (c == 'B' && ans != "") {
      ans.pop_back();
      continue;
    } else if (c == 'B' && ans == "") continue;
    ans += c;
  }
  cout << ans << endl;
}

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

using namespace std;

#define range(i, m, n) for(int i = m; i < n; i++)
#define husk(i, m, n) for(int i = m; i > n; i--)

int n;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  vector<int> a(n);
  range(i, 0, n) {
    int p;
    cin >> p;
    p--;
    a[p] = i;
  }
  int cur = 1;
  int res = 1;
  husk(i, n - 2, -1) {
    if(a[i] < a[i + 1]) cur++;
    else cur = 1;
    res = max(res, cur);
  }
  cout << n - res;
  return 0;
}


Measured memory_bytes: 1024
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

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

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

x = int(input())
a = 100
r = 1.01

m = 100
for i in range(1,3761):
    m = floor(m*r)
    if m>=x:
        print(i)
        exit()
    else:
        pass

Measured memory_bytes: 68780
#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <cassert>
#include <algorithm>

std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());

const int ms = 200200;
int par[ms], sz[ms];
int getPar(int x) { return x == par[x] ? x : par[x] = getPar(par[x]); }
void makeUnion(int a, int b) {
	//std::cout << "making union between " << a << ", " << b << '\n';
	par[getPar(a)] = getPar(b);
}

int main() {
	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
	int n;
	std::cin >> n;
	std::vector<std::pair<int, int>> a(n);
	std::vector<int> p(n);
	for(int i = 0; i < n; i++) {
		par[i] = p[i] = i;
		std::cin >> a[i].first >> a[i].second;
	}
	for(int wtf = 0; wtf < 2; wtf++) {
		for(auto &v : a) {
			std::swap(v.first, v.second);
		}
		for(int rep = 0; rep < 2; rep++) {
			std::sort(p.begin(), p.end(), [&](int v1, int v2) { return a[v1] < a[v2]; });
			std::vector<int> st;
			for(auto id : p) {
				while(!st.empty() && a[st.back()].second > a[id].second) {
					st.pop_back();
				}
				if(!st.empty()) {
					makeUnion(st.back(), id);
				}
				st.push_back(id);
			}
			for(int i = 0; i + 1 < (int) st.size(); i++) {
				makeUnion(st[i], st[i+1]);
			}
			for(auto &v : a) {
				v.first = -v.first;
				v.second = -v.second;
			}
		}
		for(int rep = 0; rep < 2; rep++) {
			std::sort(p.begin(), p.end(), [&](int v1, int v2) { return a[v1] < a[v2]; });
			std::vector<int> st;
			for(auto id : p) {
				while(!st.empty() && a[st.back()].second < a[id].second) {
					makeUnion(st.back(), id);
					st.pop_back();
				}
				st.push_back(id);
			}
			for(auto &v : a) {
				v.first = -v.first;
				v.second = -v.second;
			}
		}
	}
	for(int i = 0; i < n; i++) {
		sz[getPar(i)]++;
	}
	for(int i = 0; i < n; i++) {
		std::cout << sz[getPar(i)] << '\n';
	}
}

Measured memory_bytes: 10220
#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <deque>
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  
#include <chrono>
#include <random>
#include <time.h>
#include <fstream>
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define endl "\n"
#define all(c) begin(c),end(c)
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}
void print(vec v){for(auto e:v)cout<<e<<" ";cout<<endl;}
void print(vecll v){for(auto e:v)cout<<e<<" ";cout<<endl;}
void print(map<int,int> mp){for(auto e:mp)cout<<e.first<<" "<<e.second<<endl;cout<<endl;}


#define INF 1e9+7
#define LLINF 1e18+7
#define N 250000

template< typename Monoid >
struct SegmentTree {
  using F = function< Monoid(Monoid, Monoid) >;
 
  int sz;
  vector< Monoid > seg;
 
  const F f;
  const Monoid M1;
 
  SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz, M1);
  }
 
  void set(int k, const Monoid &x) {
    seg[k + sz] = x;
  }
 
  void build() {
    for(int k = sz - 1; k > 0; k--) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }
 
  void update(int k, const Monoid &x) {
    k += sz;
    seg[k] = x;
    while(k >>= 1) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }
 
  Monoid query(int a, int b) {
    Monoid L = M1, R = M1;
    for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if(a & 1) L = f(L, seg[a++]);
      if(b & 1) R = f(seg[--b], R);
    }
    return f(L, R);
  }
 
  Monoid operator[](const int &k) const {
    return seg[k + sz];
  }
};
//SegmentTree(n,f,M1) nで初期化　fは二項演算　M1は単位元
//set(k,x) 要素k = x
//build() 構築
//query 区間[a,b)に二項演算
//update(k,x) kをxに
//operator[k] k番目の要素
// SegmentTree< int > seg(N,[](int a,int b){return min(a,b);},INF);
//みたいに使う

main(){
    ll n=in();
    ll ans=0;
    vecll a;
    rep(i,n)a.pb(in());
    SegmentTree< ll > seg(n+1,[](ll a,ll b){return min(a,b);},LLINF);
    rep(i,n){
        seg.set(i,a[i]);
    }
    seg.build();
    rep(i,n){
        ll left,right;
        int l=-1,r=i;
        while(l<r-1){
            int mid=(l+r)/2;
            if(seg.query(mid,i+1)<a[i])l=mid;
            else r=mid;
        }
        left=r;
        l=i,r=n;
        while(l<r-1){
            int mid=(l+r)/2;
            if(seg.query(i+1,mid+1)<=a[i])r=mid;
            else l=mid;
        }
        right=l;
        ans+=a[i]*(i-left+1)*(right+1-i);
        // cout<<ans<<endl;
    }
    cout<<ans;
}

Measured memory_bytes: 6000
#include <stdio.h>

int main()
{
	int M,N;

	scanf("%d%d",&N,&M);

	int A[N];
	int a=0,i;
	double b;
	int count=0;

	for(i=0;i<N;i++)
	{
		scanf("%d",&A[i]);
		a=a + A[i];
	}
	b=(double)a / (double)(4*M);
	for(i=0;i<N;i++)
	{
		if(A[i] >= b)
			count++;
	}

	if(M > count)
	{
		printf("No\n");
	}
	else
	{
		printf("Yes\n");
	}
	return 0;
}

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

long long res = 0;
int d;

void dfs(int i, int j, vector<int> &build, const vector<int> &dig) {
	if (i > j) {
		for (int ii = 0, jj = (int) build.size() - 1; ii < jj; ++ii, --jj)
			build[jj] = -build[ii];
		long long pw = 1;
		long long sum = 0;
		for (int ii = 0; ii < (int) build.size(); ++ii) {
			sum += pw * build[ii];
			pw *= 10;
		}
		if (sum != d) return;
// 		for (auto x : build) cout << x << ' ';
// 		cout << '\n';
		long long delta = 1;
		for (int ii = 0, jj = (int) build.size() - 1; ii <= jj; ++ii, --jj) {
			int mul = 10 - abs(build[ii]);
			if (ii == 0) --mul;
// 			cout << "MUL: " << mul << endl;
			delta *= mul;
		}
		res += delta;
	} else {
		build[i] += dig[i];
		int save = build[i];
		int x = (build[i] % 10 + 10) % 10;
		for (int y = x - 10; y <= x; y += 10) if (-9 <= y && y <= 9) {
			if (i == 0 && y > 0) continue;
			if (i == j && y != 0) continue;
			build[i] = y;
			if (i + 1 < (int) build.size()) build[i + 1] = (save - y) / 10;
			dfs(i + 1, j - 1, build, dig);
		}
	}
}

int main() {
	cin >> d;
	vector<int> dig;
	for (int x = d; x > 0; x /= 10) dig.push_back(x % 10);
	for (int l = (int) dig.size(); l <= 2 * (int) dig.size(); ++l) {
		vector<int> build (l);
		dfs(0, l - 1, build, dig);
	}
	cout << res << endl;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

typedef unsigned long long ull;

int main() {
    ull n,a=1,b;
    cin>>n;
    for(ull d=2;d*d<=n;d++){
        if(n%d==0)      a=d;
    }
    b=n/a;
    cout<<a+b-2;
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define endl '\n'
#define fo(i,n) for(i=0;i<n;++i)
#define forr(i,n) for(i=n-1;i>=0;--i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

ll gcd(ll a,ll b){while(a&&b)a>b?a%=b:b%=a;return a+b;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(){
    ios_base::sync_with_stdio(false);cout.tie(NULL);
    string s;
    string::iterator it;
    cin>>s;
    ll i, j, k, unique = 0;
    for(i=1;i<s.length()-1;i++){
      if(s[i-1]!=s[i+1])
      {
        unique++;
        it = s.begin()+i;
        s.erase(it);
        i-=2;
        if(i<0)
          i = 0;
      }
    }
    // cout<<s<<endl;
    if(unique%2)
      cout<<"First"<<endl;
    else
      cout<<"Second"<<endl;
    return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;
LL dp[302][302];
LL dp2[302][302];
int N;
int M;
int main(){
        REP(i,302){
            REP(j,302){
                dp[i][j]=0;
                dp2[i][j]=0;
            }
        }
	cin>>N>>M;
	dp[0][0]=1;
	REP(k,M){
	    REP(i,N){
	        REP(j,N){
	            //進む
	            dp2[i+1][j]+=(dp[i][j]*(N-1-i));
	             dp2[i+1][j]%=1000000007;
	            //戻る
	            if(j<=i){
	               dp2[i][i]+=(dp[i][j]*(j+1));
	                dp2[i][i]%=1000000007;
	            }
	            //自己ループ
	            dp2[i][j]+=(dp[i][j]*(i-j));
	            dp2[i][j]%=1000000007;
	        }
	    }
	    REP(i,N){
	        REP(j,N){
	            dp[i][j]=(dp2[i][j]%1000000007);
	            dp2[i][j]=0;
	        }
	    }
	}
	/*REP(i,30){
	        REP(j,30){
	        cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
	        }
	    }
	    cout<<endl;
	*/
        cout<<dp[N-1][N-1]<<endl;
	return(0);
}

Measured memory_bytes: 1664
n = int(input())
l = [int(i) for i in input().split()]
count = 0

for i in range(n):
  for j in range(i + 1, n):
    for k in range(j + 1, n):
      if(l[i] != l[j] and l[i] != l[k] and l[j] != l[k]):
        if(l[i] + l[j] > l[k] and l[i] + l[k] > l[j] and l[j] + l[k] > l[i]):
          count += 1
          
print(count)


Measured memory_bytes: 68260
fun main(args: Array<String>) {
    val N = nextInt()
    val S = next()
    val ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    var ans = ""
    for (c in S) {
        val ch = c - 'A'
        ans += ALPHABET[(ch + N) % 26]
    }
    println("${ans}")
}
fun next() = readLine()!!
fun nextInt(delta: Int = 0) = Integer.parseInt(next()) + delta

Measured memory_bytes: 114092
#include <bits/stdc++.h>
 
using namespace std;
using ull = unsigned long long;
using ll = long long;
using ld = long double;
using D = double;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;
 
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define makeunique(x) sort(all(x)), (x).resize(unique(all(x)) - (x).begin())
#define rep(i, x)  for(int i = 0; i < (x); i++)
#define rrep(i, x) for(int i = (x - 1); i >= 0; i--)
#define sqrt(x) sqrt(abs(x))
#define y1 y1_1234413
#define j1 j1_235
#define y0 y0_235
#define j0 j0_256
#define fi first
#define se second
#define re return
#define prev PREV
#define next NEXT
#define sz(x) ((int)x.size())
 
template<typename T> T sqr(T a) { re a * a; }
template<typename T> T gcd(T a, T b) { re b ? gcd(b, a % b) : a; }
template<typename T> T sgn(T a) { re a > 0 ? 1 : (a < 0 ? -1 : 0); }
template<typename T> T abs(T a) { re a > 0 ? a : -a; }
 
const int inf = 2e9;
const ld st = 0.000001;
const ld pi = acos((ld)-1);
const int N = 3e3 + 10;
 
#define FILENAME ""
 
int n;
int m;

D dp[N][N];
bool was[N][N];
D a[N];

D f (int v, int k) {
	if (v == n) re (k >= (n + 1) / 2 ? 1 : 0);
	if (was[v][k]) re dp[v][k];
	was[v][k] = 1;
	dp[v][k] = f (v + 1, k + 1) * a[v] + f (v + 1, k) * ((D)1 - a[v]);
	re dp[v][k];

}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);
//  freopen(FILENAME ".in", "r", stdin);
//  freopen(FILENAME ".out", "w", stdout);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	cout << setprecision (10) << f(0, 0);
    re 0;
}

Measured memory_bytes: 79872
#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
string s;
int n,dp[100009][13];
int main() {
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>s;
    n=s.size();
	dp[0][0]=1;
	for(int i=0;i<n;i++)
		if(s[i]=='?')
			for(int j=0;j<13;j++)
				for(int k=0;k<10;k++) {
					dp[i+1][(j*10+k)%13]+=dp[i][j];
					dp[i+1][(j*10+k)%13]%=mod;
				}
		else
			for(int j=0;j<13;j++) {
				dp[i+1][(j*10+s[i]-'0')%13]+=dp[i][j];
				dp[i+1][(j*10+s[i]-'0')%13]%=mod;
			}
	cout<<dp[n][5]<<endl;
	return 0;
}

Measured memory_bytes: 5584
#include <bits/stdc++.h>
using namespace std;
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define lop ios; ll t; cin>>t; while(t--)
#define pb push_back
#define vi vector<ll>
#define vivi vector<vector<ll>> 
#define vipa vector<pair<ll,ll>>
#define F first
#define S second
#define M 1000000007
#define kl endl
typedef long long ll;
ll lcm(ll x, ll y){ll k=x*y; k/=(__gcd(x,y)); return k;}
ll power(ll x,ll y){ ll r= 1;x = x % M;if(x==0) return 0; while(y>0) {if(y&1) r=(r*x)%M; y=y>>1; x=(x*x)%M;} return r;}  
void solve()
{ 
 ll n;
 cin>>n;
 ll a=0,b=0,c=0,d=0;
 while(n--){
     string s;
     cin>>s;
     for(auto i:s){
         if(i=='C'){
             a++;break;
         }
         if(i=='W'){
             b++;break;
         }
         if(i=='L'){
             c++;break;
         }
         if(i=='R'){
             d++;break;
         }
     }
 }
 cout<<"AC x "<<a<<kl;
 cout<<"WA x "<<b<<kl;
 cout<<"TLE x "<<c<<kl;
 cout<<"RE x "<<d<<kl;
 
 
 
}
int main() 
{ 
   //lop
    solve();
	return 0; 
} 




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

int main(){
    int c[3][3];

    for(int i = 0; i < 3; i++){
        cin >> c[i][0] >> c[i][1] >> c[i][2];
    }

    int a[3];
    int b[3];
    
    a[0] = c[0][0]-c[1][0];//a1-a2
    a[1] = c[1][0]-c[2][0];//a2-a3
    a[2] = c[2][0]-c[0][0];//a3-a1
    b[0] = c[0][0]-c[0][1];//b1-b2
    b[1] = c[0][1]-c[0][2];//b2-b3
    b[2] = c[0][2]-c[0][0];//b3-b1

    int ab[3][3];
    int ba[3][3];
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            ba[i][j] = c[i][j] - c[i][(j+1)%3];
            ab[j][i] = c[j][i] - c[(j+1)%3][i];
        }
    }

    int flag = 0;
    if(ab[0][0] == ab[0][1] && ab[0][0] == ab[0][2]){
        if(ab[1][0] == ab[1][1] && ab[1][0] == ab[1][2]){
            if(ab[2][0] == ab[2][1] && ab[2][0] == ab[2][2]){
                flag = 1;
            }
        }
    }

    if(flag == 1){
        if(ba[0][0] == ba[1][0] && ba[0][0] == ba[2][0]){
            if(ba[0][1] == ba[1][1] && ba[0][1] == ba[2][1]){
                if(ba[0][2] == ba[1][2] && ba[0][2] == ba[2][2]){
                    cout << "Yes" << endl;;
                }
            }
        }
    }
    else {
        cout << "No" << endl;
    }


}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define itn int
#define int long long
#define mod 1000000007
#define fi first
#define se second
#define be begin()
#define en end()
#define re reverse
#define Set setprecision 
const int INFi=2147483647;
const long long INFl=9223372036854775807LL;
template<typename T> T abs(T a,T b){
    return max(a,b)-min(a,b);
}
template<typename T> T lcm(T a,T b){//�Ǿ����ܿ�
  return (a*b)/gcd(a,b);
}
int  gcd(int a,int b){//��������
  int c=a%b;
  while(true){
    if(c==0) break;
    a=b;
    b=c;
    c=a%b;
  }
  return b;
}
bool IsPrime(int num){
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;
    double sqrtNum = sqrt(num);
    for(int i=3;i<=sqrtNum;i+=2){
	if(num%i==0){
	    return false;
	}
    }
  return true;
}
int n,m;
int sum;
int date[10000000];
int dfs(int a=0,int b=0){
  if(b>=3) date[sum]=a,sum++;
  if(b<m){
    dfs(a*10+3,b+1);
    dfs(a*10+5,b+1);
    dfs(a*10+7,b+1);
  }
}
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin>>n;
    int c=n,d=0;
    while(true){
      if(c==0) break;
      m++;
      c/=10;
    }
    dfs();
    for(int i=0;i<sum;i++){
      if(date[i]<=n&&date[i]!=0){
	int e=0,f=0,g=0;
	while(true){
	  if(date[i]==0) break;
	  if(date[i]%10==3) e=1;
	  if(date[i]%10==5) f=1;
	  if(date[i]%10==7) g=1;
	  date[i]/=10;
	}
	if(e+f+g==3) d++;
      }
    }
    cout<<d<<"\n";
}


Measured memory_bytes: 512
n = int(input())
a = []
b = []
for _ in range(n):
  A, B = map(int, input().split())
  a.append(A)
  b.append(B)
x = 0
for i in range(1, n+1):
  a[-i] += x
  if a[-i]%b[-i] != 0: x += b[-i] - a[-i]%b[-i]
print(x)

Measured memory_bytes: 15016
import math
x,y = map(int,input().split())

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

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

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

if (x+y)%3!=0:
    print(0)
else:
    a = x-(x+y)//3
    b = y-(x+y)//3
    print(cmb(a+b,a,mod))

Measured memory_bytes: 127712
#include<iostream>
using namespace std;
int main()
{
  int A,B,C,X;
  cin>>A>>B>>C>>X;
  int res=0;
  for (int a=0; a<=A;++a){
    for ( int b=0; b<=B;++b){
      for ( int c=0; c<=C;++c){
        int total = 500*a + 100*b + 50*c;
        if (total ==X) ++res;
      }
    }
  }
  cout<<res<<endl;
}


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

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

use std::cmp::{max, min};
use std::collections::HashMap;

fn main() {
  let a = read::<String>();
  let b = read::<String>();
  let c = read::<String>();
  let A: Vec<char> = a.chars().nth(0).unwrap().to_uppercase().collect();
  let B: Vec<char> = b.chars().nth(0).unwrap().to_uppercase().collect();
  let C: Vec<char> = c.chars().nth(0).unwrap().to_uppercase().collect();

  let mut ans = String::from("");
  ans.push(A[0]);
  ans.push(B[0]);
  ans.push(C[0]);
  println!("{}", ans);
}

Measured memory_bytes: 4352