제출 #158270

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
158270		maruii	Boat (APIO16_boat)	C++14	9 / 100	11 ms	4348 KiB

boat

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
vector<int> xx(1);
int f[505][1005], s[1005], g[505][1005], A[505], B[505];

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int N; cin >> N;
	for (int i = 1; i <= N; ++i) {
		cin >> A[i] >> B[i]; B[i]++;
		xx.push_back(A[i]);
		xx.push_back(B[i]);
	}
	sort(xx.begin(), xx.end());
	xx.erase(unique(xx.begin(), xx.end()), xx.end());
	for (int i = 1; i <= N; ++i) {
		s[0] = f[i - 1][0] = 1;
		for (int j = 1; j + 1 < xx.size(); ++j) s[j] = (s[j - 1] + f[i - 1][j]) % mod;
		for (int j = 1; j + 1 < xx.size(); ++j) {
			if (A[i] <= xx[j] && xx[j + 1] <= B[i]) {
				long long n = xx[j + 1] - xx[j];
				f[i][j] = (n * s[j - 1] + g[i - 1][j]) % mod;
				g[i][j] = ((n + 1) * n / 2 % mod * s[j - 1] % mod + g[i - 1][j] * n % mod - n * (n - 1) / 2 % mod * f[i - 1][j] % mod + mod) % mod;
			}
			else {
				f[i][j] = f[i - 1][j];
				g[i][j] = g[i - 1][j];
			}
		}
	}
	int ans = 0;
	for (int i = 0; i + 1 < xx.size(); ++i) ans = (ans + f[N][i]) % mod;
	cout << ans;
	return 0;
}

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

boat.cpp: In function 'int main()':
boat.cpp:20:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j + 1 < xx.size(); ++j) s[j] = (s[j - 1] + f[i - 1][j]) % mod;
                   ~~~~~~^~~~~~~~~~~
boat.cpp:21:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j + 1 < xx.size(); ++j) {
                   ~~~~~~^~~~~~~~~~~
boat.cpp:34:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i + 1 < xx.size(); ++i) ans = (ans + f[N][i]) % mod;
                  ~~~~~~^~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42