oj.uz

Submission #259238

# Submission time Handle Problem Language Result Execution time Memory
259238 2020-08-07T12:44:47 Z vioalbert Nuclearia (CEOI15_nuclearia) C++14
30 / 100
 1000 ms 100868 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int w, h, n, q;
vector<vector<ll>> grid, pref;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> w >> h >> n;
	grid.assign(h+1, vector<ll>(w+1, 0));
	pref.assign(h+1, vector<ll>(w+1, 0));
	for(int i = 0; i < n; i++) {
		ll x, y, a, b; cin >> x >> y >> a >> b;
		for(int r = 1; r <= h; r++) {
			for(int c = 1; c <= w; c++) {
				grid[r][c] += max(0ll, a - b * (ll)max(abs(x - c), abs(y - r)));
			}
		}
	}

	for(int r = 1; r <= h; r++) {
		for(int c = 1; c <= w; c++) {
			pref[r][c] = pref[r-1][c] + pref[r][c-1] - pref[r-1][c-1] + grid[r][c];
		}
	}

	cin >> q;
	while(q--) {
		ll r1, c1, r2, c2; cin >> c1 >> r1 >> c2 >> r2;
		// cerr << r1 << ' ' << c1 << ' ' << r2 << ' ' << c2 << '\n';
		double ans = pref[r2][c2] - pref[r1-1][c2] - pref[r2][c1-1] + pref[r1-1][c1-1];
		ans /= (r2 - r1 + 1) * (c2 - c1 + 1);
		cout << (ll)(ans+0.5) << '\n';
	}

	return 0;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 98220 KB Output is correct
2 Correct 67 ms 3320 KB Output is correct
3 Correct 68 ms 2808 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 98224 KB Output is correct
2 Correct 68 ms 3192 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 39800 KB Output is correct
2 Correct 62 ms 4472 KB Output is correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 49272 KB Output is correct
2 Correct 71 ms 4768 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 100868 KB Output is correct
2 Correct 90 ms 5368 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 42720 KB Output is correct
2 Correct 67 ms 3064 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 42872 KB Output is correct
2 Correct 69 ms 4984 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 30748 KB Output is correct
2 Correct 71 ms 3960 KB Output is correct

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 98220 KB Time limit exceeded

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 98312 KB Time limit exceeded

Subtask #11
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 39680 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1096 ms 39544 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 41344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 39680 KB Time limit exceeded
2 Halted 0 ms 0 KB -