oj.uz

Submission #308378

# Submission time Handle Problem Language Result Execution time Memory
308378 2020-10-01T02:30:07 Z Dormi Packing Biscuits (IOI20_biscuits) C++14
9 / 100
 1000 ms 1386744 KB 
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
int sz(const T &a){return int(a.size());}
const int MAXN=62;
map<ll,ll> dp;//num of nums that are <= i that can be made.
ll psa[MAXN];
ll x;
ll solve(ll a){//greedy always wanna take from closest bit which is smaller, as such nothing will ever be wasted.
    if(a<0)return 0;
    if(a==0)return 1;
    if(dp.count(a))return dp[a];
    ll msb=__lg(a);
    return dp[a]=solve((1<<msb)-1)+solve(min(a,psa[msb]/x)-(1<<msb));//psa[msb]/x is largest integer s.t. x*y<=psa[i] and we use the dp to check y-2^i is good.
}
ll count_tastiness(ll X, vector<ll> a){//maytlenotsure
    x=X;
    int n=sz(a);
    dp=map<ll,ll>();
    psa[0]=a[0];
    for(int i=1;i<=60;i++){
        if(i<n)psa[i]=psa[i-1]+(ll(1)<<i)*a[i];
        else psa[i]=psa[i-1];
    }
    return solve((ll(1)<<60)-1);
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 1 ms 256 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 1 ms 256 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Execution timed out 1186 ms 1279900 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1192 ms 1386744 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Execution timed out 1171 ms 1155472 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 1 ms 256 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 1 ms 256 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Execution timed out 1186 ms 1279900 KB Time limit exceeded
17 Halted 0 ms 0 KB -