
 Code Submission Evaluation System 
Login 
HIIT Open 2018

Start:  20180526 11:00:00 
End:  20180526 16:00:00 


Tasks  Messages  Scoreboard  Statistics
CSES  HIIT Open 2018  ResultsHistory 

20180526 14:23:37  ✓ 
Task:  Find a Word 
Sender:  KnowYourArchitecture 
Submission time:  20180526 14:23:37 
Language:  C++ 
Status:  READY 
Result:  ACCEPTED 
Test results
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
string s[40];
ll ways[40][40];
char ans[1010];
pair<ll,ll> dbg[40][40];
ll mult[40][40];
int main() {
int n;
ll k;
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> s[i];
ways[n1][n1] = 1;
for (int i = n1; i >= 0; i) {
for (int j = n1; j >= 0; j) {
if (j == n1 && i == n1) continue;
ways[i][j] = ways[i][j+1] + ways[i+1][j];
}
}
map<pair<ll,ll>,set<pair<ll,pair<ll,ll>>>> old;
old[{0,ways[0][0]}].emplace(1,pair<ll,ll>(0,0));k;
mult[0][0]=1;
for (int diag = 0; diag < 2*n; diag++) {
map<pair<ll,ll>,map<char,vector<pair<ll,pair<ll,ll>>>>> nw;
for(auto& it: old){
ll i,j;
tie(i,j) = it.first;
if(i>k  j<=k)continue;
for(auto& jt : it.second){
ll x,y,cnt;
pair<ll,ll> coord;
tie(cnt,coord) = jt;
tie(x,y) = coord;
dbg[x][y] = {i,j};
ans[diag]=s[x][y];
if(x+1<n)nw[{i,j}][s[x+1][y]].emplace_back(cnt,pair<ll,ll>(x+1,y));
if(y+1<n)nw[{i,j}][s[x][y+1]].emplace_back(cnt,pair<ll,ll>(x,y+1));
}
}
old.clear();
for (auto& it : nw) {
ll lasti;
ll i,j;
tie(i,j) = it.first;
lasti=i;
for(auto &jt:it.second){
if(lasti>k)break;
ll ni=lasti;
for(auto& kt : jt.second){
ll cnt,x,y;
pair<ll,ll> coord;
tie(cnt,coord) = kt;
tie(x,y) = coord;
ni+=ways[x][y]*cnt;
mult[x][y]+=cnt;
}
if(ni>k){
for(auto& kt : jt.second){
ll cnt,x,y;
pair<ll,ll> coord;
tie(cnt,coord ) = kt;
tie(x,y) = coord;
old[{lasti,ni}].insert({mult[x][y],coord});
dbg[x][y]={lasti,ni};
}
break;
}
lasti=ni;
}
}
}
//for(int i=0;i<n;++i){for(int j=0;j<n;++j)cout<<dbg[i][j].first<<','<<dbg[i][j].second<<' ';cout<<'\n';}
//for(int i=0;i<n;++i){for(int j=0;j<n;++j)cout<<ways[i][j]<<' ';cout<<'\n';}
cout<<ans<<endl;
}
Test details
Test 1
Verdict: ACCEPTED
input 

4 1
AAAA
AAAA
AAAA
AAAA 
Test 2
Verdict: ACCEPTED
input 

4 2
AAAA
AAAA
AAAA
AAAA 
Test 3
Verdict: ACCEPTED
input 

4 10
AAAA
AAAA
AAAA
AAAA 
Test 4
Verdict: ACCEPTED
input 

4 19
AAAA
AAAA
AAAA
AAAA 
Test 5
Verdict: ACCEPTED
input 

4 20
AAAA
AAAA
AAAA
AAAA 
Test 6
Verdict: ACCEPTED
input 

4 1
QNJP
EVJU
XHZF
RXCV 
Test 7
Verdict: ACCEPTED
input 

4 2
QNJP
EVJU
XHZF
RXCV 
Test 8
Verdict: ACCEPTED
input 

4 10
QNJP
EVJU
XHZF
RXCV 
Test 9
Verdict: ACCEPTED
input 

4 19
QNJP
EVJU
XHZF
RXCV 
Test 10
Verdict: ACCEPTED
input 

4 20
QNJP
EVJU
XHZF
RXCV 
Test 11
Verdict: ACCEPTED
input 

30 1
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
... 
correct output 

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA... 
user output 

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA... 
Test 12
Verdict: ACCEPTED
input 

30 15033633249770520
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
... 
correct output 

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA... 
user output 

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA... 
Test 13
Verdict: ACCEPTED
input 

30 30067266499541040
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
... 
correct output 

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA... 
user output 

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA... 
Test 14
Verdict: ACCEPTED
input 

30 1
QNJPEVJUXHZFRXCVKBSJKUURVPLYUI
RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW
FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP
WYLTEQJBJRPSEMPOESVKFTQKEMSIAP
QHYOUWFHLJQDVTGVCSIVHNPKDWNJQC
GBUFNYPCWYNPQQMADZXQPYTAUETQSU
LURTALUCESXQWEFCOXPGXBFUIOMFBW
RJPAYRYBOCQKHOHRAWHJTITBTBTUQK
EMREBEZQUEFPCFEAYNTCYIBSMVIUPI
SCOSBRKAKZBPLLZPPOYCZRUTADFQEF
VKIJFVWGOCYMDCFXSEBAGJIRSKNYSK
FEVSYNRBXCOHWXGIRQOPNAIVYLXQOE
JNABESJIUMPKLSDJKBIGOSGCEJKNRN
SYROUHKKNTCYGDSSTYBQBYPOWUQIHS
YXZKTSAPWXLKLQGSNKTPGEAQIAHFMC
BAGQPHLNARILPPVQUYQOMTHOXNIKMZ
NLDRZQIWUYFGQXWCIQOCRXFUPKZWWY
AAROAOVNBBNVDZNZHOZGCHYAFTHHWD
DWCDSGBQZKLLXWHHWGXJQWNWENIZWZ
... 
correct output 

QNJLGFBBMJBHCCBOCEFBPLDCFGDJKB... 
user output 

QNJLGFBBMJBHCCBOCEFBPLDCFGDJKB... 
Test 15
Verdict: ACCEPTED
input 

30 15033633249770520
QNJPEVJUXHZFRXCVKBSJKUURVPLYUI
RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW
FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP
WYLTEQJBJRPSEMPOESVKFTQKEMSIAP
QHYOUWFHLJQDVTGVCSIVHNPKDWNJQC
GBUFNYPCWYNPQQMADZXQPYTAUETQSU
LURTALUCESXQWEFCOXPGXBFUIOMFBW
RJPAYRYBOCQKHOHRAWHJTITBTBTUQK
EMREBEZQUEFPCFEAYNTCYIBSMVIUPI
SCOSBRKAKZBPLLZPPOYCZRUTADFQEF
VKIJFVWGOCYMDCFXSEBAGJIRSKNYSK
FEVSYNRBXCOHWXGIRQOPNAIVYLXQOE
JNABESJIUMPKLSDJKBIGOSGCEJKNRN
SYROUHKKNTCYGDSSTYBQBYPOWUQIHS
YXZKTSAPWXLKLQGSNKTPGEAQIAHFMC
BAGQPHLNARILPPVQUYQOMTHOXNIKMZ
NLDRZQIWUYFGQXWCIQOCRXFUPKZWWY
AAROAOVNBBNVDZNZHOZGCHYAFTHHWD
DWCDSGBQZKLLXWHHWGXJQWNWENIZWZ
... 
correct output 

QNXZYLYURTAYRYZQUKZCYOPKYKLQPX... 
user output 

QNXZYLYURTAYRYZQUKZCYOPKYKLQPX... 
Test 16
Verdict: ACCEPTED
input 

30 30067266499541040
QNJPEVJUXHZFRXCVKBSJKUURVPLYUI
RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW
FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP
WYLTEQJBJRPSEMPOESVKFTQKEMSIAP
QHYOUWFHLJQDVTGVCSIVHNPKDWNJQC
GBUFNYPCWYNPQQMADZXQPYTAUETQSU
LURTALUCESXQWEFCOXPGXBFUIOMFBW
RJPAYRYBOCQKHOHRAWHJTITBTBTUQK
EMREBEZQUEFPCFEAYNTCYIBSMVIUPI
SCOSBRKAKZBPLLZPPOYCZRUTADFQEF
VKIJFVWGOCYMDCFXSEBAGJIRSKNYSK
FEVSYNRBXCOHWXGIRQOPNAIVYLXQOE
JNABESJIUMPKLSDJKBIGOSGCEJKNRN
SYROUHKKNTCYGDSSTYBQBYPOWUQIHS
YXZKTSAPWXLKLQGSNKTPGEAQIAHFMC
BAGQPHLNARILPPVQUYQOMTHOXNIKMZ
NLDRZQIWUYFGQXWCIQOCRXFUPKZWWY
AAROAOVNBBNVDZNZHOZGCHYAFTHHWD
DWCDSGBQZKLLXWHHWGXJQWNWENIZWZ
... 
correct output 

QRXZYLYURTAYRYZQUKZCYOPKYKLQPX... 
user output 

QRXZYLYURTAYRYZQUKZCYOPKYKLQPX... 