Submission #338064

#	Time	Username	Problem	Language	Result	Execution time	Memory
338064		kutbilim_one	UFO (IZhO14_ufo)	C++14	75 / 100	1766 ms	262144 KiB

ufo

/** kutbilim.one **/
#include <bits/stdc++.h>
 
using namespace std;
 
#define all(x) x.begin(),x.end()
//#define int long long
#define endl '\n'
                              /* 
ifstream in("test.txt");     
#define cin in                  */ 

int n, m, r, k, p;

void sovle1(){
    vector < vector <int> > a(1+n, vector <int> (1+m, 0));
   vector < vector <int> > sum(1+n, vector <int> (1+m, 0));
   
   set <int> col[1+m];
   set <int> row[1+n];
   set <int> col2[1+m];
   set <int> row2[1+n];
   set <int> del;
   set <int>::iterator it;
   int temp, cnt;
   
   for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
         cin >> a[i][j];
         if (a[i][j] != 0) {
            row[i].insert(j);
            col[j].insert(i);
            row2[i].insert(-j);
            col2[j].insert(-i);
         }
      }
   }
   for (int tmp = k; tmp--;) {
      char c; cin >> c;
      int pos, h; cin >> pos >> h;
      if (c == 'N') {
         if (col[pos].empty()) continue;
         int cnt = 0;
         for (auto i: col[pos]) {
            a[i][pos]--;
            if (a[i][pos] == 0) del.insert(i), row[i].erase(pos), row2[i].erase(-pos);
            cnt++;if(cnt==r)break;
         }
         for (auto i: del) {
            col[pos].erase(i);
            col2[pos].erase(-i);
         }
      } else if (c == 'S') {
         if (col2[pos].empty()) continue;
         int cnt = 0;
         for (auto i: col2[pos]) {
            a[-i][pos]--;
            if (a[-i][pos] == 0) del.insert(-i), row[-i].erase(pos), row2[-i].erase(-pos);
            cnt++;if(cnt==r)break;
         }
         for (auto i: del) {
            col[pos].erase(i);
            col2[pos].erase(-i);
         }
      } else if (c == 'W') {
         if (row[pos].empty()) continue;
         int cnt = 0;
         for (auto i: row[pos]) {
            a[pos][i]--;
            if (a[pos][i] == 0) del.insert(i), col[i].erase(pos), col2[i].erase(-pos);
            cnt++;if(cnt==r)break;
         }
         for (auto i: del) {
            row[pos].erase(i);
            row2[pos].erase(-i);
         }
      } else {
         if (row2[pos].empty()) continue;
         int cnt = 0;
         for (auto i: row2[pos]) {
            a[pos][-i]--;
            if (a[pos][-i] == 0) del.insert(-i), col[-i].erase(pos), col2[-i].erase(-pos);
            cnt++;if(cnt==r)break;
         }
         for (auto i: del) {
            row[pos].erase(i);
            row2[pos].erase(-i);
         }
      }
      del.clear();
   }
   
   for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
         sum[i][j] = a[i][j];
         sum[i][j] += sum[i-1][j];
         sum[i][j] += sum[i][j-1];
         sum[i][j] -= sum[i-1][j-1];
      }
   }
   
   int ans = 0, A, i2, j2;
   for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= m; j++) {
         i2 = i + p - 1, j2 = j + p - 1;
         if (i2 <= n && j2 <= m) {
            A = sum[i2][j2];
            A -= sum[i2][j-1];
            A -= sum[i-1][j2];
            A += sum[i-1][j-1];
            if (A > ans)
               ans = A;
         }
      }
   }
   
   cout << ans << '\n';
}

void solve2(){
	vector< vector<int> > a(n+1, vector<int>(m+1));
    for(int i = 1; i <= n; i++)
	for(int j = 1; j <= m; j++) cin >> a[i][j];
 
	while(k--){
		char side;
		int pos, h;
		cin >> side >> pos >> h;
 
		int shots = r;
		if(side == 'W'){
			for(int j = 1; j <= m && shots > 0; j++)
				if(a[pos][j] >= h) a[pos][j]--, shots--;
		}else if(side == 'E'){
		    for(int j = m; j >= 1 && shots > 0; j--)
				if(a[pos][j] >= h) a[pos][j]--, shots--;
		}else if(side == 'N'){
		    for(int i = 1; i <= n && shots > 0; i++)
				if(a[i][pos] >= h) a[i][pos]--, shots--;
		}else{
		    for(int i = n; i >= 1 && shots > 0; i--)
				if(a[i][pos] >= h) a[i][pos]--, shots--;
		}
	}
 
	vector< vector<int> > sums(n+2, vector<int>(m+1));
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
        	sums[i][j] += a[i][j] + sums[i][j-1];
        }
	}
	for(int i = 1; i <= m; i++){
		for(int j = 1; j <= n; j++){
        	sums[j][i] += sums[j-1][i];
        }
	}
	                  
	int maxx = 0;
	for(int i = p; i <= n; i++){
		for(int j = p; j <= m; j++){
			maxx = max(maxx, sums[i][j]-sums[i][j-p]-sums[i-p][j]+sums[i-p][j-p]);	
		} 
	}
	    
    cout << maxx;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> r >> k >> p;
    
    if(n*m < 100000) solve2();
    else sovle1();

    return 0;
}

Compilation message (stderr)

ufo.cpp: In function 'void sovle1()':
ufo.cpp:25:8: warning: unused variable 'temp' [-Wunused-variable]
   25 |    int temp, cnt;
      |        ^~~~
ufo.cpp:25:14: warning: unused variable 'cnt' [-Wunused-variable]
   25 |    int temp, cnt;
      |              ^~~
ufo.cpp: In function 'void solve2()':
ufo.cpp:122:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  122 |     for(int i = 1; i <= n; i++)
      |     ^~~
ufo.cpp:125:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  125 |  while(k--){
      |  ^~~~~

• Subtask 1: 75 / 100