oj.uz

Submission #696333

# Submission time Handle Problem Language Result Execution time Memory
696333 2023-02-06T09:04:37 Z garam1732 Packing Biscuits (IOI20_biscuits) C++14
12 / 100
 20 ms 780 KB 
#include "biscuits.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef __int128 ii;
ll dp[100];

ll solve(ll x, vector<ll> a, bool full) {
    if(a.empty()) return dp[0] = 1;
    ll z = *a.rbegin(); int sz = a.size();
    a.pop_back();

    if(full && dp[sz]) return dp[sz];

    ll q = z/x, res = 0;
    res += (q+1)*solve(x, a, 1);

    if(z % x) {
        ii v = (ii)(x-z%x)*(1LL<<(sz-1));
        for(int i = (int)a.size()-1; i >= 0; i--) {
            if(v == 0) break;
            else if(v >= (ii)a[i]*(1LL<<i)) {
                v -= (ii)a[i]*(1LL<<i);
                a.pop_back();
            }
            else {
                a[i] -= v/(1LL<<i);
                break;
            }
        }

        if(v == 0) res += solve(x, a, 0);
    }

    if(full) dp[sz] = res;
    return res;
}

long long count_tastiness(long long x, std::vector<long long> a) {
	for(int i = 0; i <= a.size(); i++) {
        dp[i] = 0;
        for(int j = i+1; j < a.size(); j++) {
            if(a[i]/x >= (1LL<<(j-i))-1) {
                a[i] += a[j]*(1LL<<(j-i));
                a[j] = 0;
            }
        }
	}

	return solve(x, a, 0);
}

Compilation message

biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:41:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(int i = 0; i <= a.size(); i++) {
      |                 ~~^~~~~~~~~~~
biscuits.cpp:43:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for(int j = i+1; j < a.size(); j++) {
      |                          ~~^~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Incorrect 0 ms 212 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 20 ms 780 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Incorrect 0 ms 212 KB Output isn't correct
12 Halted 0 ms 0 KB -