QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #886095 | #10019. Gold Coins | rotcar07 | TL | 0ms | 3584kb | C++23 | 883b | 2025-02-06 20:31:26 | 2025-02-06 20:31:27 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
constexpr int N=305;
int n,m,a[N][N],dp[N][N],s[N][N];
int sr[N],sc[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) cin>>a[i][j];
for(int i=1;i<=n+1;i++)
for(int j=1;j<=m+1;j++)s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
auto f=[&](int a,int b,int c,int d){return s[c][d]-s[c][b]-s[a][d]+s[a][b];};
auto cmin=[&](int&x,int y){(x>y)&&(x=y);};
for(int i=n;i>=1;i--)
for(int j=m;j>=1;j--){
sr[i-1]=sc[j-1]=0;
for(int x=i;x<=n;x++) sr[x]=sr[x-1]+(!!f(x-1,j-1,x,m));
for(int x=j;x<=m;x++) sc[x]=sc[x-1]+(!!f(i-1,x-1,n,x));
dp[i][j]=1e9;
for(int x=i;x<=n;x++)
for(int y=j;y<=m;y++)
if(!f(x,y,n,m)) cmin(dp[i][j],dp[x+1][j]+dp[i][y+1]+sc[y]*sr[x]-f(i-1,j-1,x,y));
}
cout<<dp[1][1]<<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3456kb
input:
2 3 1 0 0 0 1 1
output:
1
result:
ok answer is '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
4 4 0 1 1 1 1 1 0 0 1 1 1 1 1 0 1 0
output:
2
result:
ok answer is '2'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
7 7 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
output:
18
result:
ok answer is '18'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
1 1 0
output:
0
result:
ok answer is '0'
Test #5:
score: -100
Time Limit Exceeded
input:
300 300 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 1 0 1 0 1 1 0 1 0 1 1 1 0 0 1 1 1 1 0 1 1 0 1 1 1 0 1 1 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 0 0 1 1 0 1 1 1 0 1 0 1 1 0 0 0 0 1 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...