Submission #1060003

#TimeUsernameProblemLanguageResultExecution timeMemory
1060003dozerClosing Time (IOI23_closing)C++17
0 / 100
1024 ms9536 KiB
#include "closing.h" #include <bits/stdc++.h> using namespace std; #define sp " " #define endl "\n" #define fastio() cin.tie(0), ios_base::sync_with_stdio(0) #define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout) #define pb push_back #define pii pair<int, int> #define st first #define nd second #define LL node * 2 #define RR node * 2 + 1 #define ll long long const int modulo = 1e9 + 7; const ll INF = 2e18 + 7; int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) { vector<ll> lft, rgt; lft.pb(0), rgt.pb(0); ll sum = 0; for (int i = X - 1; i >= 0; i--){ sum += W[i]; lft.pb(lft.back() + sum); } sum = 0; for (int i = Y + 1; i < N; i++){ sum += W[i - 1]; rgt.pb(rgt.back() + sum); } ll ans = 0; //todo : no one can reach the other { vector<ll> merge(2 * N + 2, INF); for (ll i = 0; i < lft.size(); i++){ for (ll j = 0; j < rgt.size(); j++) merge[i + j] = min(merge[i + j], lft[i] + rgt[j]); } vector<ll> cost(N, 0); ll total = 0; ll GH = 0; for (ll i = X; i <= Y; i++){ if (i > X) { GH += W[i - 1]; cost[i] = GH; total += cost[i];; } ll sum = total; ll GH2 = 0; for (ll j = Y; j >= X; j--){ if (j < Y) { GH2 += W[j]; sum += max((ll)0, GH2 - cost[j]); } ll pos = upper_bound(merge.begin(), merge.end(), K - sum) - merge.begin(); if (sum <= K) ans = max(ans, pos + i - X + Y - j + 1); } } } //todo : X can reach Y { vector<ll> merge(2 * N + 2, INF); for (ll i = 0; i < lft.size(); i++){ for (ll j = 0; j < rgt.size(); j++) merge[i + j] = min(merge[i + j * 2], lft[i] + rgt[j]); } vector<ll> cost(N, 0); ll total = 0, GH = 0;; for (ll i = X + 1; i <= Y; i++){ GH += W[i - 1]; cost[i] = GH; total += cost[i]; } ll GH2 = 0; for (ll i = Y; i >= X; i--){ if (i < Y) { GH2 += W[i]; total += max((ll)0, GH2 - cost[i]); } ll pos = upper_bound(merge.begin(), merge.end(), K - total) - merge.begin(); if (total <= K) ans = max(ans, pos + Y - X + Y - i + 1); } } //todo : Y can reach X { vector<ll> merge(2 * N + 2, INF); for (ll i = 0; i < lft.size(); i++){ for (ll j = 0; j < rgt.size(); j++) merge[i + j] = min(merge[i * 2 + j], lft[i] + rgt[j]); } vector<ll> cost(N, 0); ll total = 0, GH = 0; for (ll i = Y - 1; i >= X; i--){ GH += W[i]; cost[i] = GH; total += cost[i]; } ll GH2 = 0; for (ll i = X; i <= Y; i++){ if (i > X) { GH2 += W[i - 1]; total += max((ll)0, GH2 - cost[i - 1]); } ll pos = upper_bound(merge.begin(), merge.end(), K - total) - merge.begin(); if (total <= K) ans = max(ans, pos + Y - X + i - X + 1); } } //todo : both can reach each other { vector<ll> merge(2 * N + 2, INF); for (ll i = 0; i < lft.size(); i++){ for (ll j = 0; j < rgt.size(); j++) merge[i + j] = min(merge[i * 2 + j * 2], lft[i] + rgt[j]); } vector<ll> cost(N, 0); ll total = 0, GH = 0; for (ll i = Y - 1; i >= X; i--){ GH += W[i]; cost[i] = GH; total += cost[i]; } ll GH2 = 0; for (ll i = X; i <= Y; i++){ if (i > X) { GH2 += W[i - 1]; total += max((ll)0, GH2 - cost[i - 1]); } } ll pos = upper_bound(merge.begin(), merge.end(), K - total) - merge.begin(); if (total <= K) ans = max(ans, pos + Y - X + Y - X + 1); } return ans; } /* int main() { fileio(); int Q; assert(1 == scanf("%d", &Q)); std::vector<int> N(Q), X(Q), Y(Q); std::vector<long long> K(Q); std::vector<std::vector<int>> U(Q), V(Q), W(Q); for (int q = 0; q < Q; q++) { assert(4 == scanf("%d %d %d %lld", &N[q], &X[q], &Y[q], &K[q])); U[q].resize(N[q] - 1); V[q].resize(N[q] - 1); W[q].resize(N[q] - 1); for (int i = 0; i < N[q] - 1; ++i) { assert(3 == scanf("%d %d %d", &U[q][i], &V[q][i], &W[q][i])); } } fclose(stdin); std::vector<int> result(Q); for (int q = 0; q < Q; q++) { result[q] = max_score(N[q], X[q], Y[q], K[q], U[q], V[q], W[q]); } for (int q = 0; q < Q; q++) { printf("%d\n", result[q]); } fclose(stdout); return 0; } */

Compilation message (stderr)

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:41:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (ll i = 0; i < lft.size(); i++){
      |                        ~~^~~~~~~~~~~~
closing.cpp:42:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             for (ll j = 0; j < rgt.size(); j++)
      |                            ~~^~~~~~~~~~~~
closing.cpp:72:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for (ll i = 0; i < lft.size(); i++){
      |                        ~~^~~~~~~~~~~~
closing.cpp:73:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |             for (ll j = 0; j < rgt.size(); j++)
      |                            ~~^~~~~~~~~~~~
closing.cpp:102:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for (ll i = 0; i < lft.size(); i++){
      |                        ~~^~~~~~~~~~~~
closing.cpp:103:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |             for (ll j = 0; j < rgt.size(); j++)
      |                            ~~^~~~~~~~~~~~
closing.cpp:132:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |         for (ll i = 0; i < lft.size(); i++){
      |                        ~~^~~~~~~~~~~~
closing.cpp:133:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |             for (ll j = 0; j < rgt.size(); 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...
#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...