BZOJ3308 九月的咖啡店

Orz PoPoQQQ

话说这题还有要注意的地方。。。

就是。。。不能加SLF优化，千万不能加

n = 40000，不加本机跑出来2sec，加了跑出来40sec。。。【给跪了

 /**************************************************************

     Problem: 3308

     User: rausen

     Language: C++

     Result: Accepted

     Time:27500 ms

     Memory:32752 kb

 ****************************************************************/

 #include <cstdio>

 #include <algorithm>

 #include <bitset>

 using namespace std;

 const int N = 2e4 + ;

 const int Cnt = N * ;

 const int M = Cnt * ;

 const int inf = 1e9;

 struct edges {

     int next, to, f, cost;

     edges() {}

     edges(int _n, int _t, int _f, int _c) : next(_n), to(_t), f(_f), cost(_c) {}

 } e[M];

 int n, ans, S, T;

 int first[N], tot = ;

 bitset <Cnt> not_p;

 int pr[N], tot_p, tot_a, tot_b;

 int d[N], g[N], v[N];

 inline void Add_Edges(int x, int y, int f, int c) {

     e[++tot] = edges(first[x], y, f, c), first[x] = tot;

     e[++tot] = edges(first[y], x, , -c), first[y] = tot;

 }

 inline void calc() {

     static int x;

     for (x = g[T]; x; x = g[e[x ^ ].to])

         --e[x].f, ++e[x ^ ].f;

 }

 #define y e[x].to

 inline bool spfa() {

     static int x, now, q[];

     static unsigned short l, r;

     for (x = ; x <= T; ++x)

         d[x] = -inf;

     d[S] = , v[S] = , q[] = S;

     for(l = r = ; l != r + ; ) {

         now = q[l++];

         for (x = first[now]; x; x = e[x].next) {

             if (e[x].f && d[now] + e[x].cost > d[y]) {

                 d[y] = d[now] + e[x].cost, g[y] = x;

                 if (!v[y])

                     v[y] = , q[++r] = y;

             }

         }

         v[now] = ;

     }

     return d[T] >= ;

 }

 #undef y

 inline int work() {

     int res = ;

     while (spfa())

         calc(), res += d[T];

     return res;

 }

 void get_prime(int N) {

     int i, j, k;

     for (i = ; i <= n; ++i) {

         if (!not_p[i]) pr[++tot_p] = i;

         for (j = ; j <= tot_p; ++j) {

             if ((k = i * pr[j]) > N) break;

             not_p[k] = ;

             if (i % pr[j] == ) break;

         }

     }

 }

 inline int get(int n, int p) {

     static int res;

     for (res = ; res * p <= n; res *= p);

     return res;

 }

 int main() {

     int i, j, tmp;

     scanf("%d", &n);

     get_prime(n);

     for (i = ; i <= tot_p && 1ll * pr[i] * pr[i] <= n; ++i) ++tot_a;

     for (; i <= tot_p && pr[i] *  <= n; ++i) ++tot_b;

     for (; i <= tot_p; ++i) ans += pr[i];

     S = tot_a + tot_b + , T = S + ;

 #define J j + tot_a

     for (i = ; i <= tot_a; ++i)

         Add_Edges(S, i, , ), Add_Edges(i, T, , get(n, pr[i]));

     for (j = ; j <= tot_b; ++j)

         Add_Edges(S, J, , pr[J]), Add_Edges(J, T, , );

     for (i = ; i <= tot_a; ++i)

         for (j = ; j <= tot_b; ++j)

             if ((tmp = get(n / pr[J], pr[i]) * pr[J]) > get(n, pr[i]) + pr[J])

                 Add_Edges(i, J, , tmp);

 #undef J

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

     return ;

 }

(p.s. 成功成为最慢的2333)