QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#460479#8780. Training, Round 2imtoreTL 0ms0kbC++231.0kb2024-07-01 17:29:002024-07-01 17:29:01

Judging History

你现在查看的是最新测评结果

  • [2024-07-01 17:29:01]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-07-01 17:29:00]
  • 提交

answer

#include <stdio.h>
#include <unordered_set>
#include <vector>
#include <bitset>
#include <algorithm>
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;

unordered_set<int> st[5021];
vector<pii> vc;
bitset<5021> vst[5021];

int main(){
	int n, sx, sy; scanf("%d %d %d", &n, &sx, &sy);

	st[0].insert(0);
	vst[0][0] = true;

	for(int i = 0; i < n; i++){
		int xl, xh, yl, yh; scanf("%d %d %d %d", &xl, &xh, &yl, &yh);
		xl -= sx; xl = max(xl, 0);
		xh -= sx; xh = min(xh, i);
		yl -= sy; yl = max(yl, 0);
		yh -= sy; yh = min(yh, i);

		for(int x = xl; x <= xh; x++){
			for(int y : st[x]){
				if(yl <= y && y <= yh) vc.push_back({x, y});
			}
		}

		for(auto [x, y] : vc){
			if(!vst[x+1][y]){
				st[x+1].insert(y);
				vst[x+1][y] = true;
			}
			if(!vst[x][y+1]){
				st[x].insert(y+1);
				vst[x][y+1] = true;
			}
			st[x].erase(y);
		}
		vc.clear();
	}

	int mx = 0;
	for(int x = 0; x <= n; x++){
		if(!st[x].empty()) mx = max(mx, x+*prev(st[x].end()));
	}
	return !printf("%d", mx);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

3 0 0
0 1 0 1
1 1 0 1
1 1 1 1

output:


result: