Submission #262449

#TimeUsernameProblemLanguageResultExecution timeMemory
262449yuma220284Boat (APIO16_boat)C++14
9 / 100
6 ms4360 KiB
#include "bits/stdc++.h" using namespace std; constexpr long long MOD = 1000000007; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int N; cin >> N; vector<long long> A(N), B(N), X; X.push_back(0); for (int i = 0; i < N; i++) { cin >> A[i] >> B[i]; B[i]++; X.push_back(A[i]), X.push_back(B[i]); } sort(X.begin(), X.end()); X.erase(unique(X.begin(), X.end()), X.end()); for (int i = 0; i < N; i++) { A[i] = lower_bound(X.begin(), X.end(), A[i]) - X.begin(); B[i] = lower_bound(X.begin(), X.end(), B[i]) - X.begin(); } vector<vector<long long> > DP(N + 1, vector<long long>(X.size() - 1, 0)); DP[0][0] = 1; for (int i = 0; i < N; i++) { for (int j = 0; j < X.size() - 1; j++) DP[i + 1][j] = DP[i][j]; long long SUM = 0; for (int j = 0; j < A[i]; j++) SUM += DP[i][j], SUM %= MOD; for (int j = A[i]; j < B[i]; j++) { DP[i + 1][j] += SUM * (X[j + 1] - X[j]); DP[i + 1][j] %= MOD; SUM += DP[i][j]; SUM %= MOD; } } long long ANS = 0; for (int j = 1; j < X.size() - 1; j++) { ANS += DP[N][j]; ANS %= MOD; } cout << ANS << endl; }

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:27:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for (int j = 0; j < X.size() - 1; j++) DP[i + 1][j] = DP[i][j];
      |                   ~~^~~~~~~~~~~~~~
boat.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for (int j = 1; j < X.size() - 1; j++) {
      |                  ~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...