Cod sursa(job #1747791)

Utilizator mucalmicmarcel almic mucalmic Data 25 august 2016 16:47:06
Problema Cel mai lung subsir comun Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.89 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <set>
#include <queue>          // std::priority_queue
#include <vector>         // std::vector
#include <functional>     // std::greater

using namespace std;

int main() {
    int n, k, nl, q, x, y, c, dst, d2, m;
    const int INF = 50000001;
    long long sum;
    
    ifstream myfile;
    myfile.open ("cmlsc.in");
    myfile>>n>>m;
    
    vector <int> a(n), b(m);
    vector <vector <int>> mat(n, vector <int>(m, 0));
    vector <vector <char>> dir(n, vector <char>(m, 0));
    vector <int> rez;
    
    for (int i = 0; i < n; i++)
    	myfile>>a[i];
    
    for (int i = 0; i < m; i++)
    	myfile>>b[i];
    	
    myfile.close();	
    
    if (n && m) {
    	for(int i = 0; i < m; i++){
    		if (a[0] == b[i])
     			mat[0][i] = 1;
     		dir[0][i] = 4;
     	}
     			
     	for(int i = 0; i < n; i++) {
    		if (a[i] == b[0])
     			mat[i][0] = 1;
     		dir[i][0] = 4;
     	}
     	int x, y;
     	for(int i = 1; i < n; i++) {
     		for(int j = 1; j < m; j++) {
     			x = mat[i-1][j-1];
     			y = 0;
     			if (a[i] == b[j])
     				x++;
     			if (mat[i][j-1] > x) {
     				x = mat[i][j-1];
     				y = 1;
     			}
     			if (mat[i-1][j] > x) {
     				x = mat[i-1][j];
     				y = 2;
     			}
     			
     			dir[i][j] = y;
     			mat[i][j] = x;
     			//cout<<i<<" "<<j<<" "<<x<<" "<<y<<endl;
     		}
     	}
     	
     	x = n-1;
     	y = m-1;
     	int d;
     	while (dir[x][y] < 4) {
     		d = dir[x][y];
     		if (!d) {
     			if (a[x] == b[y])
     				rez.push_back(a[x]);
     			x--;
     			y--;
     		}
     		else if(d == 1)
     			y--;
     		else
     			x--;
     	}
     	if (a[x] == b[y])
     		rez.push_back(a[x]);    
    }
    
	ofstream f2;
	f2.open ("cmlsc.out");
	n = rez.size();
	f2<<n<<endl;
	for (int i = n-1; i >= 0; i--) {
		f2<<rez[i]<<" ";
	}
		f2<<endl;
	f2.close();
    
    return 0;
}