제출 #522075

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
522075		LucaDantas	Global Warming (CEOI18_glo)	C++17	48 / 100	2097 ms	118016 KiB

glo

#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>

constexpr int maxn = 2e5+10;
constexpr unsigned int maxT = 0x7fffffff;

struct BIT {
	std::map<int, int> bit;
	void upd(unsigned int x, int v) {
		for(x++; x < maxT; x += x&-x)
			bit[x] = std::max(bit[x], v);
	}
	int query(int x) {
		int ans = 0;
		for(x++; x > 0; x -= x&-x)
			ans = std::max(ans, bit[x]);
		return ans;
	}
	void clear() { bit.clear(); }
} bit;

int t[maxn], dp[maxn], max_temp;

int main() {
	int n, x; scanf("%d %d", &n, &x);
	for(int i = 0; i < n; i++)
		scanf("%d", t+i), max_temp = std::max(max_temp, t[i]);

	for(int i = 0; i < n; i++) {
		dp[i] = bit.query(t[i]-1)+1;
		bit.upd(t[i], dp[i]);
	}

	bit.clear();

	int ans = 0;
	std::reverse(t, t+n);
	std::reverse(dp, dp+n);
	for(int i = 0; i < n; i++)
		t[i] = max_temp - t[i] + 1;

	for(int i = 0; i < n; i++) {
		ans = std::max(ans, dp[i] + bit.query(t[i] + x - 1));
		bit.upd(t[i], bit.query(t[i]-1)+1);
	}

	printf("%d\n", ans);
}

컴파일 시 표준 에러 (stderr) 메시지

glo.cpp: In function 'int main()':
glo.cpp:27:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |  int n, x; scanf("%d %d", &n, &x);
      |            ~~~~~^~~~~~~~~~~~~~~~~
glo.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |   scanf("%d", t+i), max_temp = std::max(max_temp, t[i]);
      |   ~~~~~^~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 0 / 10
• Subtask 5: 20 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25