oj.uz

Submission #782890

# Submission time Handle Problem Language Result Execution time Memory
782890 2023-07-14T11:07:00 Z canadavid1 Raisins (IOI09_raisins) C++14
85 / 100
 5000 ms 33532 KB 
#include <bits/stdc++.h>
using namespace std;
#define all(x) begin(x),end(x)
using pii = pair<int,int>;
using i64 = int64_t;
using i8 = int;
vector<vector<int>> raisins;

map<tuple<i8,i8,i8,i8>,i64> memo;
i64 min_cost(i8 sx,i8 sy,i8 ex,i8 ey)
{
    // memoize
    if(ey-sy <= 1 && ex - sx <= 1)
    {
        return 0;
    }
    if (memo.count({sx,sy,ex,ey})) return memo[{sx,sy,ex,ey}];
    // rows
    int cost = /* count of raisins present */ 0;
    for(int i = sy; i < ey; i++) for(int j = sx; j < ex; j++) cost += raisins[i][j];
    i64 mincost = INT64_MAX;
    for(int i = sx+1; i < ex;i++)
    {
        mincost = min(mincost,min_cost(sx,sy,i,ey)+min_cost(i,sy,ex,ey));
    }
    for(int i = sy+1; i < ey;i++)
    {
        mincost = min(mincost,min_cost(sx,sy,ex,i)+min_cost(sx,i,ex,ey));
    }
    memo[{sx,sy,ex,ey}] = cost + mincost;
    return cost + mincost;
}




int main()
{
    int N,M;
    cin >> N >> M;
    raisins.assign(N,vector<int>(M));
    for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) cin >> raisins[i][j];
    cout << min_cost(0,0,M,N) << "\n";

}

Subtask #1
85.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 7 ms 468 KB Output is correct
7 Correct 9 ms 552 KB Output is correct
8 Correct 208 ms 3108 KB Output is correct
9 Correct 372 ms 4972 KB Output is correct
10 Correct 601 ms 6900 KB Output is correct
11 Correct 509 ms 5864 KB Output is correct
12 Correct 2033 ms 16620 KB Output is correct
13 Correct 3619 ms 25080 KB Output is correct
14 Correct 933 ms 8736 KB Output is correct
15 Correct 4414 ms 29440 KB Output is correct
16 Correct 248 ms 3456 KB Output is correct
17 Correct 1479 ms 13376 KB Output is correct
18 Execution timed out 5078 ms 33492 KB Time limit exceeded
19 Execution timed out 5085 ms 33532 KB Time limit exceeded
20 Execution timed out 5032 ms 33324 KB Time limit exceeded