# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1105779 |
2024-10-27T18:02:58 Z |
Faggi |
Raisins (IOI09_raisins) |
C++11 |
|
150 ms |
131072 KB |
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll INF = LLONG_MAX;
ll calc(vector<vector<ll>>mat)
{
ll n=mat.size(),m=mat[0].size(), res=0,j,i,tot=0,I,D,dif,miDIFi,mii,mij,miDIFj;
vector<vector<ll>>iz,der;
///CASOS BASE
if(n==1&&m==2)
{
res=mat[0][0]+mat[0][1];
return res;
}
else if(n==2&&m==1)
{
res=mat[0][0]+mat[1][0];
return res;
}
else if(n==1&&m==3)
{
res=mat[0][0]+mat[0][1]+mat[0][2];
res+=min(mat[0][0],mat[0][2])+mat[0][1];
return res;
}
else if(n==3&&m==1)
{
res=mat[0][0]+mat[1][0]+mat[2][0];
res+=min(mat[0][0],mat[2][0])+mat[1][0];
return res;
}
///ARREGLOS DE CALCULO
vector<ll>filas(n),columnas(m);
for(i=0; i<n; i++)
{
for(j=0; j<m; j++)
{
res+=mat[i][j];
tot+=mat[i][j];
filas[i]+=mat[i][j];
columnas[j]+=mat[i][j];
}
}
///CORTES VERTICALES
I=0; D=tot;
miDIFj=INF;
mij=1;
for(i=0; i<m; i++)
{
I+=columnas[i];
D-=columnas[i];
dif=abs(I-D);
if(miDIFj>dif)
{
miDIFj=dif;
mij=i;
}
}
///CORTES HORIZONTALES
I=0; D=tot;
miDIFi=INF;
mii=1;
for(i=0; i<n; i++)
{
I+=filas[i];
D-=filas[i];
dif=abs(I-D);
if(miDIFi>dif)
{
miDIFi=dif;
mii=i;
}
}
///ELEGIR CORTE
if(miDIFi>miDIFj)
{
iz.resize(n,vector<ll>(mij+1));
der.resize(n,vector<ll>(m-(mij+1)));
for(i=0; i<n; i++)
{
for(j=0; j<=mij; j++)
{
iz[i][j]=mat[i][j];
}
}
for(i=0; i<n; i++)
{
for(j=mij+1; j<m; j++)
{
der[i][(j-mij)-1]=mat[i][j];
}
}
res+=calc(iz)+calc(der);
}
else
{
iz.resize(mii+1,vector<ll>(m));
der.resize((n-(mii+1)),vector<ll>(m));
for(i=0; i<=mii; i++)
{
for(j=0; j<m; j++)
{
iz[i][j]=mat[i][j];
}
}
for(i=mii+1; i<n; i++)
{
for(j=0; j<m; j++)
{
der[(i-(mii+1))][j]=mat[i][j];
}
}
res+=calc(iz)+calc(der);
}
return res;
}
int main()
{
ll n, m, i, j;
cin >> n >> m;
vector<vector<ll>>mat(n,vector<ll>(m));
for(i=0; i<n; i++)
{
for(j=0; j<m; j++)
{
cin >> mat[i][j];
}
}
cout << calc(mat);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
150 ms |
131072 KB |
Execution killed with signal 9 |
2 |
Correct |
1 ms |
504 KB |
Output is correct |
3 |
Runtime error |
134 ms |
131072 KB |
Execution killed with signal 9 |
4 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
5 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |
6 |
Correct |
1 ms |
336 KB |
Output is correct |
7 |
Runtime error |
137 ms |
131072 KB |
Execution killed with signal 9 |
8 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
9 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
10 |
Runtime error |
148 ms |
131072 KB |
Execution killed with signal 9 |
11 |
Runtime error |
137 ms |
131072 KB |
Execution killed with signal 9 |
12 |
Runtime error |
139 ms |
131072 KB |
Execution killed with signal 9 |
13 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
14 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
15 |
Runtime error |
140 ms |
131072 KB |
Execution killed with signal 9 |
16 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
17 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
18 |
Runtime error |
147 ms |
131072 KB |
Execution killed with signal 9 |
19 |
Correct |
2 ms |
336 KB |
Output is correct |
20 |
Incorrect |
1 ms |
592 KB |
Output isn't correct |