oj.uz

Submission #404292

# Submission time Handle Problem Language Result Execution time Memory
404292 2021-05-14T06:41:52 Z AmineTrabelsi Packing Biscuits (IOI20_biscuits) C++14
33 / 100
 981 ms 574532 KB 
// official solution testing
#include "biscuits.h"
#include <vector>
#include <unordered_map>
using namespace std;

const int x_max = 3e5+1;
long long dp[61][2*x_max];

long long f(int idx, long long w, long long x, vector<long long> &a) {
    if(idx==60) return 1;
    if(dp[idx][w]!=-1) return dp[idx][w];
    return dp[idx][w] = f(idx+1, (w+a[idx])/2, x, a) + (w+a[idx]>=x ? f(idx+1, (w+a[idx]-x)/2, x, a) : 0);
}

void merge_biscuits(long long x, vector<long long> &a) {
    while(a.size()<61) a.push_back(0);
    for(int i=0; i<(int)a.size(); i++) {
        if(a[i]>x+1) {
            a[i+1] += (a[i]-x)/2;
            a[i] -= ((a[i]-x)/2)*2;
        }
    }
}

long long count_tastiness(long long x, std::vector<long long> a) {
    for(int i=0; i<=60; i++) {
        for(int j=0; j<=2*x; j++) {
            dp[i][j] = -1;
        }
    }
    merge_biscuits(x, a);
    return f(0, 0, x, a);
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Runtime error 14 ms 336 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

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

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 10272 KB Output is correct
2 Correct 19 ms 9184 KB Output is correct
3 Correct 28 ms 9816 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 70 ms 10316 KB Output is correct
9 Correct 50 ms 10316 KB Output is correct
10 Correct 1 ms 716 KB Output is correct
11 Correct 2 ms 844 KB Output is correct
12 Correct 10 ms 1956 KB Output is correct
13 Correct 70 ms 10188 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 981 ms 574532 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Runtime error 14 ms 336 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -