제출 #545989

#제출 시각아이디문제언어결과실행 시간메모리
545989aryan12Cloud Computing (CEOI18_clo)C++17
100 / 100
738 ms2644 KiB
#include <bits/stdc++.h> using namespace std; #define int long long mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); const int N = 1e5 + 5, INF = 1e16; vector<vector<int> > dp(2, vector<int> (N, -INF)); bool cmp(array<int, 3> a, array<int, 3> b) { if(a[1] == b[1]) { return a[0] > b[0]; //so that stores are before customers } return a[1] > b[1]; } void Solve() { int n; cin >> n; vector<array<int, 3> > store(n); vector<array<int, 3> > together; for(int i = 0; i < n; i++) { cin >> store[i][0] >> store[i][1] >> store[i][2]; together.push_back({store[i][0], store[i][1], -store[i][2]}); } int m; cin >> m; vector<array<int, 3> > customer(m); for(int i = 0; i < m; i++) { cin >> customer[i][0] >> customer[i][1] >> customer[i][2]; together.push_back({-customer[i][0], customer[i][1], customer[i][2]}); } sort(together.begin(), together.end(), cmp); dp[0][0] = 0; for(int i = 0; i < together.size(); i++) { //cout << together[i][0] << " " << together[i][1] << " " << together[i][2] << "\n"; int cur = (i + 1) % 2, prev = i % 2; for(int j = 0; j < N; j++) { dp[cur][j] = dp[prev][j]; } if(together[i][0] > 0) //it is a store { for(int j = together[i][0]; j < N; j++) { dp[cur][j] = max(dp[cur][j], dp[prev][j - together[i][0]] + together[i][2]); } } else { for(int j = 0; j < N + together[i][0]; j++) //together[i][0] is actually -ve { dp[cur][j] = max(dp[cur][j], dp[prev][j - together[i][0]] + together[i][2]); } } } int ans = 0; int x = together.size(); int cur = x % 2; for(int i = 0; i < N; i++) { ans = max(ans, dp[cur][i]); } cout << ans << "\n"; } int32_t main() { auto begin = std::chrono::high_resolution_clock::now(); ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; //cin >> t; while(t--) { Solve(); } auto end = std::chrono::high_resolution_clock::now(); auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; return 0; }

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

clo.cpp: In function 'void Solve()':
clo.cpp:41:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(int i = 0; i < together.size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...