oj.uz

Submission #526096

# Submission time Handle Problem Language Result Execution time Memory
526096 2022-02-13T17:23:55 Z Deepesson Raisins (IOI09_raisins) C++17
15 / 100
 617 ms 27508 KB 
#include <bits/stdc++.h>
#define MAX 51
int tab[MAX][MAX];
int N,M;
int sumed[MAX][MAX];
int t(int x,int y) {
    if(x<0||y<0)return 0;
    return sumed[x][y];
}
int subrec(int x1,int y1,int x2,int y2) {
    return t(x2,y2)-t(x2,y1-1)-t(x1-1,y2)+t(x1-1,y1-1);
}
int resp[MAX][MAX][MAX][MAX];
bool exist[MAX][MAX][MAX][MAX];
int dp(int x1,int y1,int x2,int y2) {
    if(x1==x2&&y1==y2)return 0;
    if(exist[x1][y1][x2][y2])return resp[x1][y1][x2][y2];
    exist[x1][y1][x2][y2]=true;
    int custo = subrec(x1,y1,x2,y2);
    int best = 1000;
    for(int i = x1;i!=x2;++i) {
        best = std::min(best,(int)(dp(x1,y1,i,y2)+dp(i+1,y1,x2,y2)));
    }
    for(int i = y1;i!=y2;++i) {
        best = std::min(best,(int)(dp(x1,y1,x2,i)+dp(x1,i+1,x2,y2)));
    }
    return resp[x1][y1][x2][y2]=best+custo;
}
int main()
{
    std::cin >> N >> M;
    for(int i = 0; i != N;++i) {
        for(int j = 0; j != M;++j) {
            std::cin>> tab[i][j];
        }
    }
    for(int i = 0; i != N;++i) {
        int val = 0;
        for(int j = 0; j != M;++j) {
            val += tab[i][j];
            sumed[i][j]=val;
            if(i)sumed[i][j]+=sumed[i-1][j];
        }
    }
    std::cout << dp(0,0,N-1,M-1) << std::endl;
}

Subtask #1
15.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Incorrect 1 ms 588 KB Output isn't correct
6 Incorrect 1 ms 1088 KB Output isn't correct
7 Incorrect 1 ms 1228 KB Output isn't correct
8 Incorrect 9 ms 3788 KB Output isn't correct
9 Incorrect 14 ms 5036 KB Output isn't correct
10 Incorrect 20 ms 5964 KB Output isn't correct
11 Incorrect 17 ms 5196 KB Output isn't correct
12 Incorrect 60 ms 9924 KB Output isn't correct
13 Incorrect 117 ms 12576 KB Output isn't correct
14 Incorrect 28 ms 6440 KB Output isn't correct
15 Incorrect 126 ms 13876 KB Output isn't correct
16 Incorrect 11 ms 4812 KB Output isn't correct
17 Incorrect 51 ms 9592 KB Output isn't correct
18 Incorrect 323 ms 21008 KB Output isn't correct
19 Incorrect 514 ms 25680 KB Output isn't correct
20 Incorrect 617 ms 27508 KB Output isn't correct