Code Submission Evaluation System Login

CSES - HIIT Open 2017

HIIT Open 2017

Contest start:2017-05-27 11:00:00
Contest end:2017-05-27 16:00:00

Task list | Submit code | Submissions | Messages | Scoreboard


History
2017-05-27 15:12:02
2017-05-27 15:07:54
2017-05-27 15:04:51
Task:Median string
Sender:Ace of Spades
Submission time:2017-05-27 15:12:02
Status:READY
Result:ACCEPTED

Show test data

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:50:21: warning: array subscript has type 'char' [-Wchar-subscripts]
        if(a1) t[a[i]]++;
                     ^
input/code.cpp:51:21: warning: array subscript has type 'char' [-Wchar-subscripts]
        if(b1) t[b[j]]++;
                     ^
input/code.cpp:52:21: warning: array subscript has type 'char' [-Wchar-subscripts]
        if(c1) t[c[k]]++;
                     ^
input/code.cpp:54:23: warning: array subscript has type 'char' [-Wchar-subscripts]
        if(a1 && t[a[i]] > 1) q = a[i];
                       ^
input/code.cpp:55:23: warning: array subscript has type 'char' [-Wchar-subscripts]
        if(b1 && t[b[j]] > 1) q = b[j];
                       ^
input/code.cpp:56:23: warning: array subscript has type 'char' [-Wchar-subscripts]
        if(c1 && t[c[k]] > 1) q = c[k];
                       ^
input/code.cpp:71:21: warning: array subscript has type 'char' [-Wchar-subscripts]
        if(a1) t[a[i]]--;
                     ^
input/code.cpp:72:21: warning: array subscript has type 'char' [-Wchar-subscripts]
        if(b1) t[b[j]]--;
                     ^
input/code.cpp:73:21: warning: array subscript has type 'char' [-Wchar-subscripts]
        if(c1) t[c[k]]--;
                     ^

Code

#include <bits/stdc++.h>
using namespace std;
string dp2[51][51][51];
int dp[51][51][51];
int main() {
    for(int i = 0; i < 51; ++i) {
	for(int j = 0; j < 51; ++j) {
	    for(int k = 0; k < 51; ++k) {
		dp[i][j][k] = 1e9;
	    }
	}
    }
    string a,b,c;
    cin>>a>>b>>c;
    int an, bn, cn;
    an = a.size();
    bn = b.size();
    cn = c.size();
    int t[200] = {0};
    dp[0][0][0] = 0;
    for(int i = 0; i <= an; ++i) {
	for(int j = 0; j <= bn; ++j) {
	    for(int k = 0; k <= cn; ++k) {
		if(i < an) {
		    if(dp[i+1][j][k] > dp[i][j][k]+1) {
			dp[i+1][j][k] = dp[i][j][k]+1;
			dp2[i+1][j][k] = dp2[i][j][k];
		    }
		}
		if(j < bn) {
		    if(dp[i][j+1][k] > dp[i][j][k]+1) {
			dp[i][j+1][k] = dp[i][j][k]+1;
			dp2[i][j+1][k] = dp2[i][j][k];
		    }
		}
		if(k < cn) {
		    if(dp[i][j][k+1] > dp[i][j][k]+1) {
			dp[i][j][k+1] = dp[i][j][k]+1;
			dp2[i][j][k+1] = dp2[i][j][k];
		    }
		}
		for(int a1 = 0; a1 < 2; ++a1) {
		    for(int b1 = 0; b1 < 2; ++b1) {
			for(int c1 = 0; c1 < 2; ++c1) {
			    if(i+a1 > an || j+b1 > bn || k+c1 > cn) continue;
			    int cost = 0;
			    if(a1 == 0) ++cost;
			    if(b1 == 0) ++cost;
			    if(c1 == 0) ++cost;
			    if(a1) t[a[i]]++;
			    if(b1) t[b[j]]++;
			    if(c1) t[c[k]]++;
			    char q = 0;
			    if(a1 && t[a[i]] > 1) q = a[i];
			    if(b1 && t[b[j]] > 1) q = b[j];
			    if(c1 && t[c[k]] > 1) q = c[k];
			    if(q == 0) {
				if(a1) q = a[i];
				if(b1) q = b[j];
				if(c1) q = c[k];
			    }
			    if(a1) cost += (a[i] != q);
			    if(b1) cost += (b[j] != q);
			    if(c1) cost += (c[k] != q);
			    if(dp[i+a1][j+b1][k+c1] > dp[i][j][k] + cost) {
				dp[i+a1][j+b1][k+c1] = dp[i][j][k] + cost;
				dp2[i+a1][j+b1][k+c1] = dp2[i][j][k];
				dp2[i+a1][j+b1][k+c1].push_back(q);

			    }
			    if(a1) t[a[i]]--;
			    if(b1) t[b[j]]--;
			    if(c1) t[c[k]]--;
			}
		    }
		}
		if(i != an || j != bn || k != cn) 
		dp2[i][j][k].clear();
	    }
	}
    }
    cout<<dp2[an][bn][cn]<<endl;
}