Pagini recente » Cod sursa (job #1360269) | Cod sursa (job #1308763) | Cod sursa (job #2930962) | Cod sursa (job #623776) | Cod sursa (job #2774199)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdlib>
#define sw(x,y)x^=y,y^=x,x^=y
#define min(x,y)x<y?x:y
#define max(x,y)x>y?x:y
using namespace std;
ofstream out("rayman.out");
class InParser {
private:
FILE *fin;
char *buff;
int sp;
char read_ch() {
++sp;
if (sp == 4096) {
sp = 0;
fread(buff, 1, 4096, fin);
}
return buff[sp];
}
public:
InParser(const char* nume) {
fin = fopen(nume, "r");
buff = new char[4096]();
sp = 4095;
}
InParser& operator >> (int &n) {
char c;
while (!isdigit(c = read_ch()) && c != '-');
int sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
InParser& operator >> (long long &n) {
char c;
n = 0;
while (!isdigit(c = read_ch()) && c != '-');
long long sgn = 1;
if (c == '-') {
n = 0;
sgn = -1;
} else {
n = c - '0';
}
while (isdigit(c = read_ch())) {
n = 10 * n + c - '0';
}
n *= sgn;
return *this;
}
};
InParser in("rayman.in");
long long n,m,i,j,k,l,h[15][100001],r[15][100001],e[15][15],u[15][1000001][2],o[15][100001],v[15],sr,se,www;
struct t{int i,j;}a[10000000];
int main () {
ios_base::sync_with_stdio(false);
//cin.tie(NULL);
//cout.tie(NULL);
in>>n>>m;
for(i=0;i<n;i++)
for(j=0;j<m;j++)in>>h[i][j];
for(i=0;i<n;i++)
for(j=0;j<m;j++)in>>r[i][j];
for(i=0;i<n;i++)
for(j=0;j<n;j++)in>>e[i][j];
for(i=0;i<n;i++)
for(j=m-1;j>=0;j--){
k=j+1;
while(h[i][k]>h[i][j])k=o[i][k];
o[i][j]=k,u[i][j][0]=u[i][k][0]+1,u[i][j][1]=u[i][k][1]+r[i][j];
if(u[i][j][0]>u[i][v[i]][0])
v[i]=j;
else if(u[i][j][1]<u[i][v[i]][0]&&u[i][j][0]==u[i][v[i]][0])
v[i]=j;
www=k;
while(++www<=m){
if(u[i][www][0]==u[i][k][0]&&u[i][www][1]<u[i][k][1])
{
k=www;
o[i][j]=k,u[i][j][0]=u[i][k][0]+1,u[i][j][1]=u[i][k][1]+r[i][j];
if(u[i][j][0]>u[i][v[i]][0])
v[i]=j;
else if(u[i][j][1]<u[i][v[i]][0]&&u[i][j][0]==u[i][v[i]][0])
v[i]=j;
}
}
}
//for(i=0;i<n;i++)
//{for(j=0;j<m;j++)cout<<u[i][j][0]<<' ';cout<<' '<<v[i]<<'\n';}
for(i=0;i<n;i++)
for(j=v[i];j<m;j=o[i][j])
a[l].i=i,a[l].j=j,l++;
sort(a,a+l,[](t a,t b){return h[a.i][a.j]>h[b.i][b.j];});
//for(i=0;i<l;i++)cout<<a[i].i+1<<' '<<a[i].j+1<<'\n';
for(i=0;i<n;i++)
sr+=u[i][v[i]][1];
for(i=1;i<l;i++)
se+=e[a[i-1].i][a[i].i];
out<<l<<' '<<sr<<' '<<se;
}