# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
535860 |
2022-03-11T14:42:40 Z |
cig32 |
Raisins (IOI09_raisins) |
C++17 |
|
810 ms |
21460 KB |
#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define mkt make_tuple
#define debug printf
#define all(x) x.begin(),x.end()
#define lp(i,a,b) for(int i = a ; i< b ; i++)
#define ss second
#define ff first
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define mk make_pair
const int MAX = 52 ;
const int inf = 1e9+10 ;
using namespace std ;
int N , M ;
int grid[MAX][MAX] ;
int dp[MAX][MAX][MAX][MAX] ;
int get(int a1, int b1, int a2, int b2) { return grid[a2][b2] - grid[a1-1][b2] - grid[a2][b1-1] + grid[a1-1][b1-1] ; }
int solve(int a1, int b1, int a2, int b2 )
{
int &ptr = dp[a1][b1][a2][b2] ;
if( ptr != 0 || (a1 == a2 && b1 == b2) ) return ptr ;
ptr = inf ;
for(int i = b1 ; i < b2 ; i++ )
ptr = min( ptr , solve( a1, b1 , a2 , i ) + solve(a1, i+1, a2, b2) ) ;
for(int i = a1 ; i <a2 ; i++ )
ptr = min( ptr , solve(a1, b1, i , b2) + solve(i+1, b1, a2, b2) ) ;
// debug("%d %d %d %d -> %d\n" , a1, b1, a2, b2 , ptr + get(a1,b1,a2,b2)) ;
return ptr += get(a1,b1,a2,b2) ;
}
int main()
{
scanf("%d%d", &N , &M ) ;
lp(i,1,N+1)
lp(j,1,M+1)
{
scanf("%d",&grid[i][j] ) ;
grid[i][j] += -grid[i-1][j-1] + grid[i-1][j] + grid[i][j-1] ;
}
printf("%d\n", solve(1,1,N,M) ) ;
}
Compilation message
raisins.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
4 | #pragma GCC optimization ("O3")
|
raisins.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
5 | #pragma GCC optimization ("unroll-loops")
|
raisins.cpp: In function 'int main()':
raisins.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
50 | scanf("%d%d", &N , &M ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~
raisins.cpp:54:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | scanf("%d",&grid[i][j] ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
308 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
1 ms |
852 KB |
Output is correct |
7 |
Correct |
1 ms |
852 KB |
Output is correct |
8 |
Correct |
9 ms |
2644 KB |
Output is correct |
9 |
Correct |
15 ms |
3656 KB |
Output is correct |
10 |
Correct |
23 ms |
4308 KB |
Output is correct |
11 |
Correct |
18 ms |
3708 KB |
Output is correct |
12 |
Correct |
68 ms |
7424 KB |
Output is correct |
13 |
Correct |
116 ms |
9464 KB |
Output is correct |
14 |
Correct |
34 ms |
4752 KB |
Output is correct |
15 |
Correct |
143 ms |
10480 KB |
Output is correct |
16 |
Correct |
11 ms |
3644 KB |
Output is correct |
17 |
Correct |
53 ms |
7476 KB |
Output is correct |
18 |
Correct |
384 ms |
16340 KB |
Output is correct |
19 |
Correct |
672 ms |
20072 KB |
Output is correct |
20 |
Correct |
810 ms |
21460 KB |
Output is correct |