Submission #526096

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
526096	2022-02-13 17:23:55	Deepesson	Raisins (IOI09_raisins)	C++17	15 / 100	617 ms	27508 KiB

raisins

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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()
{
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 15 / 100