Cod sursa(job #2774199)

Utilizator AndreidreiGresoiu Liviu-Andrei Andreidrei Data 10 septembrie 2021 12:41:28
Problema Invers modular Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.69 kb
#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;
}