Submission #798489

#TimeUsernameProblemLanguageResultExecution timeMemory
798489Sam_a17Homecoming (BOI18_homecoming)C++17
100 / 100
187 ms180680 KiB
#define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> // #include <atcoder/all> #include <cstdio> using namespace std; #ifndef ONLINE_JUDGE #define dbg(x) cerr << #x <<" "; print(x); cerr << endl; #else #define dbg(x) #endif #define sz(x) (int((x).size())) #define len(x) (int)x.length() #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define clr(x) (x).clear() #define blt(x) __builtin_popcount(x) #define uniq(x) x.resize(unique(all(x)) - x.begin()); #define popf pop_front #define popb pop_back #define ld long double #define ll long long void print(long long t) {cerr << t;} void print(int t) {cerr << t;} void print(string t) {cerr << t;} void print(char t) {cerr << t;} void print(double t) {cerr << t;} void print(unsigned long long t) {cerr << t;} void print(long double t) {cerr << t;} template <class T, class V> void print(pair <T, V> p); template <class T> void print(vector <T> v); template <class T> void print(set <T> v); template <class T, class V> void print(map <T, V> v); template <class T> void print(multiset <T> v); template <class T> void print(T v[],T n) {cerr << "["; for(int i = 0; i < n; i++) {cerr << v[i] << " ";} cerr << "]";} template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";} template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";} #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; #define nl '\n' // for random generations mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count()); // mt19937 myrand(131); // for grid problems int dx[8] = {1,0,-1,0,1,-1,1,-1}; int dy[8] = {0,1,0,-1,1,1,-1,-1}; char ch[4] = {'v', '>', '^', '<'}; long long ka() { long long x = 0; bool z = false; while (1) { char y = getchar(); if (y == '-') z = true; else if ('0' <= y && y <= '9') x = x * 10 + y - '0'; else { if (z) x *= -1; return x; } } } // lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6 void fastIO() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); } // file in/out void setIO(string str = "") { fastIO(); if (str != "") { freopen((str + ".in").c_str(), "r", stdin); freopen((str + ".out").c_str(), "w", stdout); } else if(str == "input") { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); } } // Indexed Set template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; const long long inf = -1e16; long long solve(int N, int K, int *A, int *B) { vector<long long> a(2 * N), b(2 * N), pa(N), pb(N); int n = N, k = K; long long ans = 0; for(int i = 0; i < N; i++) { a[i] = A[i]; b[i] = B[i]; ans += a[i] - b[i]; pa[i] = a[i]; pb[i] = b[i]; if(i) { pa[i] += pa[i - 1]; pb[i] += pb[i - 1]; } } ans = max(ans, 0ll); if(k == n) { return ans; } for(int t = 0; t <= 1; t++) { vector<long long> dp(n + 1), take(n + 1); if(t == 0) { take[0] = 0; } else { take[0] = a[0] - pb[k - 1]; } dp[0] = take[0]; if(t == 1) { for(int i = 1; i < n; i++) { if(i + k - 1 < n) { take[i] = max(take[i - 1] + a[i] - b[i + k - 1], dp[i - 1] + a[i] - (pb[i + k - 1] - pb[i - 1])); } else { take[i] = max(take[i - 1] + a[i], dp[i - 1] + a[i] - (pb[n - 1] - pb[i - 1])); } dp[i] = max(dp[i - 1], take[i]); } } else { for(int i = 1; i < n; i++) { if(i + k - 1 < n) { if(i == 1) { take[i] = dp[i - 1] + a[i] - (pb[i + k - 1] - pb[i - 1]); } else { take[i] = max(take[i - 1] + a[i] - b[i + k - 1], dp[i - 1] + a[i] - (pb[i + k - 1] - pb[i - 1])); } } else { if(i == 1) { take[i] = dp[i - 1] + a[i] - (pb[n - 1] - pb[i - 1] + pb[i + k - 1 - n]); } else { take[i] = max(take[i - 1] + a[i] - b[(i + k - 1) % n], dp[i - 1] + a[i] - (pb[n - 1] - pb[i - 1] + pb[i + k - 1 - n])); } } dp[i] = max(dp[i - 1], take[i]); } } for(int i = 0; i < n; i++) { ans = max(ans, dp[i]); } } return ans; }

Compilation message (stderr)

homecoming.cpp: In function 'void setIO(std::string)':
homecoming.cpp:89:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
homecoming.cpp:90:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
homecoming.cpp:92:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
homecoming.cpp:93:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |     freopen("output.txt", "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...