| Task: | Thin Ice |
| Sender: | Victor Vatn |
| Submission time: | 2024-03-06 19:07:07 +0200 |
| Language: | C++ (C++17) |
| Status: | READY |
| Result: | 54 |
| group | verdict | score |
|---|---|---|
| #1 | ACCEPTED | 17 |
| #2 | ACCEPTED | 12 |
| #3 | ACCEPTED | 11 |
| #4 | TIME LIMIT EXCEEDED | 0 |
| #5 | ACCEPTED | 14 |
| #6 | TIME LIMIT EXCEEDED | 0 |
| test | verdict | time | group | |
|---|---|---|---|---|
| #1 | ACCEPTED | 0.00 s | 1, 5, 6 | details |
| #2 | ACCEPTED | 0.00 s | 1, 5, 6 | details |
| #3 | ACCEPTED | 0.00 s | 1, 5, 6 | details |
| #4 | ACCEPTED | 0.00 s | 1, 5, 6 | details |
| #5 | ACCEPTED | 0.00 s | 1, 5, 6 | details |
| #6 | ACCEPTED | 0.00 s | 1, 5, 6 | details |
| #7 | ACCEPTED | 0.00 s | 1, 5, 6 | details |
| #8 | ACCEPTED | 0.00 s | 1, 5, 6 | details |
| #9 | ACCEPTED | 0.00 s | 1, 2, 5, 6 | details |
| #10 | ACCEPTED | 0.14 s | 2, 6 | details |
| #11 | ACCEPTED | 0.10 s | 2, 6 | details |
| #12 | ACCEPTED | 0.13 s | 2, 6 | details |
| #13 | ACCEPTED | 0.09 s | 2, 6 | details |
| #14 | ACCEPTED | 0.10 s | 2, 6 | details |
| #15 | ACCEPTED | 0.12 s | 2, 6 | details |
| #16 | ACCEPTED | 0.12 s | 2, 6 | details |
| #17 | ACCEPTED | 0.13 s | 2, 6 | details |
| #18 | ACCEPTED | 0.13 s | 2, 6 | details |
| #19 | ACCEPTED | 0.12 s | 2, 6 | details |
| #20 | ACCEPTED | 0.10 s | 2, 6 | details |
| #21 | ACCEPTED | 0.08 s | 2, 6 | details |
| #22 | ACCEPTED | 0.00 s | 3, 4, 5, 6 | details |
| #23 | ACCEPTED | 0.00 s | 3, 4, 5, 6 | details |
| #24 | ACCEPTED | 0.00 s | 3, 4, 5, 6 | details |
| #25 | ACCEPTED | 0.00 s | 3, 4, 5, 6 | details |
| #26 | ACCEPTED | 0.00 s | 3, 4, 5, 6 | details |
| #27 | ACCEPTED | 0.00 s | 3, 4, 5, 6 | details |
| #28 | TIME LIMIT EXCEEDED | -- | 4, 6 | details |
| #29 | TIME LIMIT EXCEEDED | -- | 4, 6 | details |
| #30 | TIME LIMIT EXCEEDED | -- | 4, 6 | details |
| #31 | TIME LIMIT EXCEEDED | -- | 4, 6 | details |
| #32 | TIME LIMIT EXCEEDED | -- | 4, 6 | details |
| #33 | TIME LIMIT EXCEEDED | -- | 4, 6 | details |
| #34 | TIME LIMIT EXCEEDED | -- | 4, 6 | details |
| #35 | ACCEPTED | 0.01 s | 5, 6 | details |
| #36 | ACCEPTED | 0.01 s | 5, 6 | details |
| #37 | ACCEPTED | 0.01 s | 5, 6 | details |
| #38 | ACCEPTED | 0.01 s | 5, 6 | details |
| #39 | ACCEPTED | 0.01 s | 5, 6 | details |
| #40 | ACCEPTED | 0.01 s | 5, 6 | details |
| #41 | ACCEPTED | 0.01 s | 5, 6 | details |
| #42 | WRONG ANSWER | 0.82 s | 6 | details |
| #43 | TIME LIMIT EXCEEDED | -- | 6 | details |
| #44 | WRONG ANSWER | 0.72 s | 6 | details |
| #45 | TIME LIMIT EXCEEDED | -- | 6 | details |
| #46 | TIME LIMIT EXCEEDED | -- | 6 | details |
| #47 | TIME LIMIT EXCEEDED | -- | 6 | details |
| #48 | TIME LIMIT EXCEEDED | -- | 6 | details |
Code
// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (ll i = (a); i < (b); ++i)
#define per(i, a, b) for (ll i = (b) - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (ll)x.size()
#define pb push_back
#define debug(x) cout<<#x<<" = "<<x<<endl
#define umap unordered_map
#define uset unordered_set
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vll> vvll;
const ll INF = 1'000'000'007;
struct UnionFind {
vll p,rank;
ll n;
UnionFind(ll N) : n(N) {
p.resize(n);
rep(i,0,n) p[i]=i;
rank.assign(n,0);
}
ll find(ll i) { return p[i]==i?i:p[i]=find(p[i]); }
bool unite(ll i,ll j) {
i=find(i);
j=find(j);
if(i==j) return 0;
if(rank[i]<rank[j]) swap(i,j);
p[j]=i;
if(rank[i]==rank[j]) ++rank[i];
return 1;
}
};
ll rows,cols,n;
vll vals;
vvll graph;
vll counts;
void dfs(ll u,ll p,ll mind,ll steps) {
if(!steps) return;
mind=min(mind,vals[u]);
++counts[mind];
trav(v,graph[u]) if(v!=p) dfs(v,u,mind,steps-1);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
cin>>rows>>cols;
n=rows*cols;
graph.resize(n);
ll maxd=0;
rep(i,0,rows) rep(j,0,cols) {
ll d;
cin>>d;
vals.pb(d);
maxd=max(maxd,d);
}
vector<pair<ll,pll>> edges;
rep(i,0,rows) rep(j,0,cols) {
ll u=i*cols+j;
if(i+1<rows) {
ll v=(i+1)*cols+j;
edges.pb({min(vals[u],vals[v]),{u,v}});
}
if(j+1<cols) {
ll v=i*cols+j+1;
edges.pb({min(vals[u],vals[v]),{u,v}});
}
}
sort(all(edges),greater<>());
UnionFind ufds(n);
trav(edge,edges) {
ll u,v;
tie(u,v)=edge.second;
if(ufds.unite(u,v)) {
graph[u].pb(v);
graph[v].pb(u);
//cout<<vals[u]<<' '<<vals[v]<<endl;
}
}
//cout<<endl;
ll steps=n+1;
if(n>1000) steps=5;
ll ans=0;
vpll roots;
rep(row,0,rows) {
rep(j,0,2) {
ll col=0;
if(j) col=cols-1;
ll u=row*cols+col;
roots.emplace_back(vals[u],u);
}
}
rep(col,0,cols) {
rep(j,0,2) {
ll row=0;
if(j) row=rows-1;
ll u=row*cols+col;
roots.emplace_back(vals[u],u);
}
}
trav(item,roots) {
counts.assign(maxd+1,0);
ll u=item.second;
dfs(u,u,INF,steps);
ll curans=0;
rep(i,0,maxd+1) curans+=min(i-curans,counts[i]);
ans=max(ans,curans);
}
cout<<ans<<endl;
return 0;
}Test details
Test 1
Group: 1, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 4 4 9 11 5 7 7 9 14 3 1 3 2 3 11 4 14 8 |
| correct output |
|---|
| 10 |
| user output |
|---|
| 10 |
Test 2
Group: 1, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 5 3 10 7 11 8 5 5 12 9 10 3 13 9 ... |
| correct output |
|---|
| 10 |
| user output |
|---|
| 10 |
Test 3
Group: 1, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 4 4 3 2 2 2 5 1 1 1 8 4 1 1 7 6 2 1 |
| correct output |
|---|
| 8 |
| user output |
|---|
| 8 |
Test 4
Group: 1, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 3 5 1 11 1 3 5 4 12 7 8 7 13 14 14 9 4 |
| correct output |
|---|
| 14 |
| user output |
|---|
| 14 |
Test 5
Group: 1, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 5 3 11 8 12 11 11 12 6 2 3 11 8 13 ... |
| correct output |
|---|
| 12 |
| user output |
|---|
| 12 |
Test 6
Group: 1, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 3 5 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 |
| correct output |
|---|
| 14 |
| user output |
|---|
| 14 |
Test 7
Group: 1, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 4 4 12 8 6 5 12 9 6 1 10 1 3 2 8 1 1 1 |
| correct output |
|---|
| 12 |
| user output |
|---|
| 12 |
Test 8
Group: 1, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 4 4 8 3 15 14 10 12 2 4 5 16 9 6 7 13 1 11 |
| correct output |
|---|
| 13 |
| user output |
|---|
| 13 |
Test 9
Group: 1, 2, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 4 4 4 1 1 2 3 5 4 2 2 2 1 2 1 4 3 4 |
| correct output |
|---|
| 4 |
| user output |
|---|
| 4 |
Test 10
Group: 2, 6
Verdict: ACCEPTED
| input |
|---|
| 10 20000 5 3 2 1 3 2 3 3 4 5 1 1 2 3 5 ... |
| correct output |
|---|
| 5 |
| user output |
|---|
| 5 |
Test 11
Group: 2, 6
Verdict: ACCEPTED
| input |
|---|
| 10 20000 1 2 1 2 1 2 1 2 1 1 1 1 2 1 1 ... |
| correct output |
|---|
| 3 |
| user output |
|---|
| 3 |
Test 12
Group: 2, 6
Verdict: ACCEPTED
| input |
|---|
| 10 20000 3 2 2 3 1 2 1 4 4 3 1 4 3 2 4 ... |
| correct output |
|---|
| 5 |
| user output |
|---|
| 5 |
Test 13
Group: 2, 6
Verdict: ACCEPTED
| input |
|---|
| 20000 10 1 1 3 1 2 1 1 1 1 1 1 2 2 1 1 1 1 2 1 1 2 1 1 1 2 2 1 1 1 2 1 1 1 1 1 1 1 1 1 1 ... |
| correct output |
|---|
| 4 |
| user output |
|---|
| 4 |
Test 14
Group: 2, 6
Verdict: ACCEPTED
| input |
|---|
| 10 20000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
| correct output |
|---|
| 3 |
| user output |
|---|
| 3 |
Test 15
Group: 2, 6
Verdict: ACCEPTED
| input |
|---|
| 10 20000 3 1 3 1 2 1 2 3 2 2 1 2 1 1 2 ... |
| correct output |
|---|
| 3 |
| user output |
|---|
| 3 |
Test 16
Group: 2, 6
Verdict: ACCEPTED
| input |
|---|
| 10 20000 1 2 2 2 1 2 3 1 2 2 2 1 2 2 2 ... |
| correct output |
|---|
| 4 |
| user output |
|---|
| 4 |
Test 17
Group: 2, 6
Verdict: ACCEPTED
| input |
|---|
| 10 20000 3 3 2 3 2 3 2 2 2 2 2 1 3 2 1 ... |
| correct output |
|---|
| 4 |
| user output |
|---|
| 4 |
Test 18
Group: 2, 6
Verdict: ACCEPTED
| input |
|---|
| 10 20000 1 3 3 1 1 4 3 3 3 1 2 2 1 3 1 ... |
| correct output |
|---|
| 5 |
| user output |
|---|
| 5 |
Test 19
Group: 2, 6
Verdict: ACCEPTED
| input |
|---|
| 7 28571 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ... |
| correct output |
|---|
| 3 |
| user output |
|---|
| 3 |
Test 20
Group: 2, 6
Verdict: ACCEPTED
| input |
|---|
| 28571 7 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 ... |
| correct output |
|---|
| 5 |
| user output |
|---|
| 5 |
Test 21
Group: 2, 6
Verdict: ACCEPTED
| input |
|---|
| 447 447 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ... |
| correct output |
|---|
| 3 |
| user output |
|---|
| 3 |
Test 22
Group: 3, 4, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 1 100 46 23 23 55 37 17 30 32 25 71 ... |
| correct output |
|---|
| 30 |
| user output |
|---|
| 30 |
Test 23
Group: 3, 4, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 1 100 8 13 12 11 15 15 15 19 18 21 2... |
| correct output |
|---|
| 76 |
| user output |
|---|
| 76 |
Test 24
Group: 3, 4, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 1 100 94 94 94 95 95 91 97 100 92 98... |
| correct output |
|---|
| 95 |
| user output |
|---|
| 95 |
Test 25
Group: 3, 4, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 1 100 83 83 83 83 83 83 83 83 83 83 ... |
| correct output |
|---|
| 83 |
| user output |
|---|
| 83 |
Test 26
Group: 3, 4, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 1 100 33 34 35 38 38 40 41 42 42 45 ... |
| correct output |
|---|
| 95 |
| user output |
|---|
| 95 |
Test 27
Group: 3, 4, 5, 6
Verdict: ACCEPTED
| input |
|---|
| 1 100 57 1 80 39 18 63 30 86 85 55 8... |
| correct output |
|---|
| 29 |
| user output |
|---|
| 29 |
Test 28
Group: 4, 6
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 1 200000 138736 14949 12344 104147 1333... |
| correct output |
|---|
| 1806 |
| user output |
|---|
| (empty) |
Test 29
Group: 4, 6
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 1 200000 141245 141090 141163 141286 14... |
| correct output |
|---|
| 155109 |
| user output |
|---|
| (empty) |
Test 30
Group: 4, 6
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 1 200000 102358 102469 102440 102402 10... |
| correct output |
|---|
| 152388 |
| user output |
|---|
| (empty) |
Test 31
Group: 4, 6
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 1 200000 180410 160820 160820 180614 18... |
| correct output |
|---|
| 160832 |
| user output |
|---|
| (empty) |
Test 32
Group: 4, 6
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 1 200000 198270 198270 198270 198270 19... |
| correct output |
|---|
| 198270 |
| user output |
|---|
| (empty) |
Test 33
Group: 4, 6
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 1 200000 1 1 3 2 1 1 2 3 6 6 6 7 8 9 10... |
| correct output |
|---|
| 199995 |
| user output |
|---|
| (empty) |
Test 34
Group: 4, 6
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 1 200000 14737 162555 44228 170991 1340... |
| correct output |
|---|
| 1902 |
| user output |
|---|
| (empty) |
Test 35
Group: 5, 6
Verdict: ACCEPTED
| input |
|---|
| 31 32 669 792 226 189 860 737 291 83... |
| correct output |
|---|
| 565 |
| user output |
|---|
| 565 |
Test 36
Group: 5, 6
Verdict: ACCEPTED
| input |
|---|
| 10 100 730 698 339 743 536 702 94 556... |
| correct output |
|---|
| 529 |
| user output |
|---|
| 529 |
Test 37
Group: 5, 6
Verdict: ACCEPTED
| input |
|---|
| 32 31 633 613 618 605 635 638 668 67... |
| correct output |
|---|
| 678 |
| user output |
|---|
| 678 |
Test 38
Group: 5, 6
Verdict: ACCEPTED
| input |
|---|
| 142 7 983 930 963 926 979 962 962 966 930 963 924 928 928 926 926 929 929 922 931 931 978 929 929 929 922 959 928 964 ... |
| correct output |
|---|
| 934 |
| user output |
|---|
| 934 |
Test 39
Group: 5, 6
Verdict: ACCEPTED
| input |
|---|
| 31 32 977 977 977 977 977 977 977 97... |
| correct output |
|---|
| 977 |
| user output |
|---|
| 977 |
Test 40
Group: 5, 6
Verdict: ACCEPTED
| input |
|---|
| 50 20 1 27 14 23 38 48 56 3 12 9 6 2... |
| correct output |
|---|
| 997 |
| user output |
|---|
| 997 |
Test 41
Group: 5, 6
Verdict: ACCEPTED
| input |
|---|
| 20 50 481 532 624 290 965 58 448 872... |
| correct output |
|---|
| 504 |
| user output |
|---|
| 504 |
Test 42
Group: 6
Verdict: WRONG ANSWER
| input |
|---|
| 447 447 6474 27185 108482 124481 16058... |
| correct output |
|---|
| 88202 |
| user output |
|---|
| 24 |
Test 43
Group: 6
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 1000 200 27722 57131 197677 184858 9285... |
| correct output |
|---|
| 89324 |
| user output |
|---|
| (empty) |
Test 44
Group: 6
Verdict: WRONG ANSWER
| input |
|---|
| 447 447 70928 73154 72640 74764 75237 ... |
| correct output |
|---|
| 181096 |
| user output |
|---|
| 23 |
Test 45
Group: 6
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 7 28571 193031 185883 171670 185794 17... |
| correct output |
|---|
| 171680 |
| user output |
|---|
| (empty) |
Test 46
Group: 6
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 10 20000 191628 191628 191628 191628 19... |
| correct output |
|---|
| 191628 |
| user output |
|---|
| (empty) |
Test 47
Group: 6
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 200 1000 3550 2640 3791 4248 4257 4504 ... |
| correct output |
|---|
| 199997 |
| user output |
|---|
| (empty) |
Test 48
Group: 6
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 1000 200 198379 62425 88013 50967 49098... |
| correct output |
|---|
| 89131 |
| user output |
|---|
| (empty) |