| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 341140 |
2020-12-29T03:51:45 Z |
tengiz05 |
UFO (IZhO14_ufo) |
C++17 |
|
1193 ms |
126424 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
template<class T> bool chmin(T& a, const T& b) {return a>b? a=b, true:false;}
template<class T> bool chmax(T& a, const T& b) {return a<b? a=b, true:false;}
const int mod = 1e9+7, N = 1005;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val)-1;}
int n, m, k, r, P;
vector<int> decreased;
struct segtree{
int sz;
vector<int> t;
void build(int n, vector<int> v){
assert((int)v.size() == n+1);
sz=1;
while(sz < n)sz<<=1;
t.assign(sz*2, 0);
for(int i=0;i<n;i++){
t[i+sz] = v[i+1];
}for(int i=sz-1;i>0;i--){
t[i] = max(t[i<<1], t[i<<1|1]);
}
}
void decrease_it(int pos){
pos += sz;
for(t[pos]--; pos > 1; pos >>= 1)t[pos>>1] = max(t[pos], t[pos^1]);
}
int remaining;
int height;
void going(int L, int R, int x){
if(remaining == 0 || t[x] < height)return;
if(R-L == 1){
t[x]--;
remaining--;
decreased.pb(x-sz+1);
return;
}int mid = (L+R)/2;
going(L, mid, x<<1);
going(mid, R, x<<1|1);
t[x] = max(t[x<<1], t[x<<1|1]);
}
void going_in_reverse(int L, int R, int x){
if(remaining == 0 || t[x] < height)return;
if(R-L == 1){
t[x]--;
remaining--;
decreased.pb(x-sz+1);
return;
}int mid = (L+R)/2;
going_in_reverse(mid, R, x<<1|1);
going_in_reverse(L, mid, x<<1);
t[x] = max(t[x<<1], t[x<<1|1]);
}
void decrease_them(int h){
decreased.clear();
remaining = r;
height = h;
going(0, sz, 1);
}
void decrease_them_in_reverse(int h){
decreased.clear();
remaining = r;
height = h;
going_in_reverse(0, sz, 1);
}
int get(int pos){
return t[pos+sz];
}
};
void solve(int test_case){
int i, j;
cin >> n >> m >> r >> k >> P;
vector<vector<int>> a(n+1, vector<int> (m+1));
vector<vector<int>> pr(n+1, vector<int> (m+1));
vector<segtree> row(n+1);
vector<segtree> col(m+1);
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
cin >> a[i][j];
}
}
for(i=1;i<=n;i++){
row[i].build(m, a[i]);
}
for(j=1;j<=m;j++){
vector<int> tmp;
tmp.pb(0);
for(i=1;i<=n;i++)tmp.pb(a[i][j]);
col[j].build(n, tmp);
}
while(k--){
char typ;
cin >> typ;
int pos, height;
cin >> pos >> height;
if(typ == 'N'){
int x=1, y=pos;
col[y].decrease_them(height);
for(auto pos : decreased){
row[pos].decrease_it(y-1);
}
}else if(typ == 'S'){
int x=n, y=pos;
col[y].decrease_them_in_reverse(height);
for(auto pos : decreased){
row[pos].decrease_it(y-1);
}
}else if(typ == 'E'){
int x=pos, y=m;
row[x].decrease_them_in_reverse(height);
for(auto pos : decreased){
col[pos].decrease_it(x-1);
}
}else {
int x=pos, y=1;
row[x].decrease_them(height);
for(auto pos : decreased){
col[pos].decrease_it(x-1);
}
}
}
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
a[i][j] = row[i].get(j-1);
}
}
/* for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
cout << a[i][j] << ' ';
}cout << '\n';
}*/
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
pr[i][j] = pr[i][j-1] + a[i][j];
}
for(j=1;j<=m;j++){
pr[i][j] += pr[i-1][j];
}
}
int ans = 0;
for(i=P;i<=n;i++){
for(j=P;j<=m;j++){
int area = pr[i][j] + pr[i-P][j-P];
area -= pr[i-P][j];
area -= pr[i][j-P];
chmax(ans, area);
}
}cout << ans << '\n';
return;
}
signed main(){
FASTIO;
#define MULTITEST 0
#if MULTITEST
int _T;
cin >> _T;
for(int T_CASE = 1; T_CASE <= _T; T_CASE++)
solve(T_CASE);
#else
solve(1);
#endif
return 0;
}
Compilation message
ufo.cpp: In function 'void solve(long long int)':
ufo.cpp:105:8: warning: unused variable 'x' [-Wunused-variable]
105 | int x=1, y=pos;
| ^
ufo.cpp:111:8: warning: unused variable 'x' [-Wunused-variable]
111 | int x=n, y=pos;
| ^
ufo.cpp:117:15: warning: unused variable 'y' [-Wunused-variable]
117 | int x=pos, y=m;
| ^
ufo.cpp:123:15: warning: unused variable 'y' [-Wunused-variable]
123 | int x=pos, y=1;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
492 KB |
Output is correct |
| 4 |
Correct |
8 ms |
876 KB |
Output is correct |
| 5 |
Correct |
46 ms |
4076 KB |
Output is correct |
| 6 |
Correct |
138 ms |
30572 KB |
Output is correct |
| 7 |
Correct |
245 ms |
69468 KB |
Output is correct |
| 8 |
Correct |
186 ms |
69468 KB |
Output is correct |
| 9 |
Correct |
283 ms |
65736 KB |
Output is correct |
| 10 |
Correct |
330 ms |
69468 KB |
Output is correct |
| 11 |
Correct |
281 ms |
56436 KB |
Output is correct |
| 12 |
Correct |
329 ms |
69532 KB |
Output is correct |
| 13 |
Correct |
410 ms |
77504 KB |
Output is correct |
| 14 |
Correct |
504 ms |
56384 KB |
Output is correct |
| 15 |
Correct |
644 ms |
69596 KB |
Output is correct |
| 16 |
Correct |
206 ms |
56256 KB |
Output is correct |
| 17 |
Correct |
940 ms |
77504 KB |
Output is correct |
| 18 |
Correct |
196 ms |
63720 KB |
Output is correct |
| 19 |
Correct |
288 ms |
77256 KB |
Output is correct |
| 20 |
Correct |
1193 ms |
126424 KB |
Output is correct |
