Task: | Ruudukko |
Sender: | PT |
Submission time: | 2015-01-29 16:06:04 +0200 |
Language: | C++ |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 17 |
#2 | ACCEPTED | 42 |
#3 | ACCEPTED | 41 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.06 s | 1 | details |
#2 | ACCEPTED | 0.06 s | 1 | details |
#3 | ACCEPTED | 0.05 s | 1 | details |
#4 | ACCEPTED | 0.06 s | 1 | details |
#5 | ACCEPTED | 0.07 s | 1 | details |
#6 | ACCEPTED | 0.07 s | 2 | details |
#7 | ACCEPTED | 0.07 s | 2 | details |
#8 | ACCEPTED | 0.07 s | 2 | details |
#9 | ACCEPTED | 0.07 s | 2 | details |
#10 | ACCEPTED | 0.07 s | 2 | details |
#11 | ACCEPTED | 0.34 s | 3 | details |
#12 | ACCEPTED | 0.36 s | 3 | details |
#13 | ACCEPTED | 0.34 s | 3 | details |
#14 | ACCEPTED | 0.34 s | 3 | details |
#15 | ACCEPTED | 0.34 s | 3 | details |
Code
#include<bits/stdc++.h>using namespace std;typedef long long ll;int n;string m[500];string b[500][500];string bestCol = "";void sett(int x, int y) {if(x == 0) {b[y][x] = b[y - 1][x] + m[y][x];}else if(y == 0) {b[y][x] = b[y][x - 1] + m[y][x];} else {b[y][x] = min(b[y - 1][x], b[y][x - 1]) + m[y][x];}}int main() {cin.sync_with_stdio(0);cin >> n;for(int y = 0; y < n; ++y) {cin >> m[y];}b[0][0] = m[0][0];for(int xs = 1; xs < 2 * n - 1; ++xs) {int d = max(0, xs - (n - 1));for(int ys = d; ys <= min(xs, n - 1); ++ys) {int x = xs - ys;int y = ys;// cout << xs << " " << x << " " << y << "\n";sett(x, y);}string minStr = "";minStr.push_back('Z' + 1);for(int ys = d; ys <= min(xs, n - 1); ++ys) {int x = xs - ys;int y = ys;minStr = min(minStr, b[y][x]);}for(int ys = d; ys <= min(xs, n - 1); ++ys) {int x = xs - ys;int y = ys;if(b[y][x] > minStr) {b[y][x].clear();b[y][x].push_back('Z' + 2);} else {b[y][x].clear();b[y][x].push_back(m[y][x]);}}// cout << "minStr: '" << minStr << "'\n";bestCol += minStr.back();}cout << m[0][0] << bestCol << "\n";}
Test details
Test 1
Group: 1
Verdict: ACCEPTED
input |
---|
5 AAAAA AAAAA AAAAA AAAAA ... |
correct output |
---|
AAAAAAAAB |
user output |
---|
AAAAAAAAB |
Test 2
Group: 1
Verdict: ACCEPTED
input |
---|
5 ABABA BABAB ABABA BABAB ... |
correct output |
---|
ABABABABA |
user output |
---|
ABABABABA |
Test 3
Group: 1
Verdict: ACCEPTED
input |
---|
5 WRYIU TWLKH UJMJC GRDJW ... |
correct output |
---|
WRWJMDJWK |
user output |
---|
WRWJMDJWK |
Test 4
Group: 1
Verdict: ACCEPTED
input |
---|
5 RUEAE ZYHHW KDBPD DXREW ... |
correct output |
---|
RUEAEWDWX |
user output |
---|
RUEAEWDWX |
Test 5
Group: 1
Verdict: ACCEPTED
input |
---|
5 SRGYR MYDOB GNOVM SZOZK ... |
correct output |
---|
SMGNOOLTU |
user output |
---|
SMGNOOLTU |
Test 6
Group: 2
Verdict: ACCEPTED
input |
---|
100 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA... |
correct output |
---|
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA... |
user output |
---|
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA... |
Test 7
Group: 2
Verdict: ACCEPTED
input |
---|
100 ABABABABABABABABABABABABABABAB... |
correct output |
---|
ABABABABABABABABABABABABABABAB... |
user output |
---|
ABABABABABABABABABABABABABABAB... |
Test 8
Group: 2
Verdict: ACCEPTED
input |
---|
100 FWOVNYKNMMQCNHJGUYPNEDXGVVGONC... |
correct output |
---|
FWDBDECKBHKIACOVUCJGDJOHAYIBHO... |
user output |
---|
FWDBDECKBHKIACOVUCJGDJOHAYIBHO... |
Test 9
Group: 2
Verdict: ACCEPTED
input |
---|
100 ETGCJABWKMAAEOQXWFFYMDJBMNKMQK... |
correct output |
---|
EAARGLBRLHCDHHBPABHDAJBEEBHQBE... |
user output |
---|
EAARGLBRLHCDHHBPABHDAJBEEBHQBE... |
Test 10
Group: 2
Verdict: ACCEPTED
input |
---|
100 GNWMLJNHSBAADUFCSGIZMWHZTVDHNR... |
correct output |
---|
GEGOFRDKBNLLEUOPOEQCEFMTKANLNC... |
user output |
---|
GEGOFRDKBNLLEUOPOEQCEFMTKANLNC... |
Test 11
Group: 3
Verdict: ACCEPTED
input |
---|
500 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA... |
correct output |
---|
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA... |
user output |
---|
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA... |
Test 12
Group: 3
Verdict: ACCEPTED
input |
---|
500 ABABABABABABABABABABABABABABAB... |
correct output |
---|
ABABABABABABABABABABABABABABAB... |
user output |
---|
ABABABABABABABABABABABABABABAB... |
Test 13
Group: 3
Verdict: ACCEPTED
input |
---|
500 HGADXTSFXYIEMDWMFIVQGHTACFUPYI... |
correct output |
---|
HGADEJOGAKPJCRAHTABRSDLAVGBFAG... |
user output |
---|
HGADEJOGAKPJCRAHTABRSDLAVGBFAG... |
Test 14
Group: 3
Verdict: ACCEPTED
input |
---|
500 SBLNMAZESQVGWAPZYHQJMQTNGMEZWS... |
correct output |
---|
SBLCAMDHILGIDRCIDUNMMAHFYCENOS... |
user output |
---|
SBLCAMDHILGIDRCIDUNMMAHFYCENOS... |
Test 15
Group: 3
Verdict: ACCEPTED
input |
---|
500 AOXYXRYFWPYWQDPWXQITLHQQUAYZAJ... |
correct output |
---|
AOJLDOAPBGEKSGCNKBUMKAJCCWCOOD... |
user output |
---|
AOJLDOAPBGEKSGCNKBUMKAJCCWCOOD... |