Submission #969121

#TimeUsernameProblemLanguageResultExecution timeMemory
969121TrendBattlesGym Badges (NOI22_gymbadges)C++14
51 / 100
2080 ms19520 KiB
//https://oj.uz/problem/view/NOI22_gymbadges #include <bits/stdc++.h> using namespace std; using lli = int64_t; #define INFILE "NOI22_gymbadges.inp" #define OUTFILE "NOI22_gymbadges.out" int main() { ios::sync_with_stdio(0); cin.tie(0); if (fopen(INFILE, "r")) { freopen(INFILE, "r", stdin); freopen(OUTFILE, "w", stdout); } int N; cin >> N; vector <int> X(N), L(N); for (int& v : X) cin >> v; for (int& v : L) cin >> v; if (*max_element(L.begin(), L.end()) == *min_element(L.begin(), L.end())) { sort(X.begin(), X.end()); int ans = N; lli sum = 0; for (int i = 0; i < N; ++i) { if (sum > L[0]) { ans = i; break; } sum += X[i]; } cout << ans; return 0; } vector <int> order(N); iota(order.begin(), order.end(), 0); sort(order.begin(), order.end(), [&] (int u, int v) { return X[u] + L[u] < X[v] + L[v]; }); // for (int i = 0; i < N; ++i) cerr << order[i] << ' '; // cerr << '\n'; // for (int i = 0; i < N; ++i) cerr << X[order[i]] << ' '; // cerr << '\n'; // for (int i = 0; i < N; ++i) cerr << L[order[i]] << ' '; // cerr << '\n'; const lli inf = 0x3f3f3f3f3f3f3f3f; vector <lli> dp(N + 1, inf); dp[0] = 0; for (int i = 0; i < N; ++i) { for (int j = N; j; --j) { if (dp[j - 1] <= L[order[i]]) { dp[j] = min(dp[j], dp[j - 1] + X[order[i]]); } } // cerr << "DEBUG: " << i << '\n'; // for (int j = 1; j <= N; ++j) { // if (dp[j] == inf) cerr << "-1 "; // else cerr << dp[j] << ' '; // } // cerr << '\n'; } for (int i = N; i >= 0; --i) { if (dp[i] < inf) { cout << i; return 0; } } return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:11:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |         freopen(INFILE, "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:12:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |         freopen(OUTFILE, "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...