제출 #783285

#제출 시각아이디문제언어결과실행 시간메모리
783285Sam_a17메기 농장 (IOI22_fish)C++17
84 / 100
639 ms113052 KiB
#define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> //#include "temp.cpp" #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 uniq(x) x.resize(unique(all(x)) - x.begin()); #define blt __builtin_popcount #define pb push_back #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(long double t) {cerr << t;} void print(unsigned long long t) {cerr << t;} #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; #define nl '\n' // Indexed Set template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; 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, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } 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(vector <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> void print(Tree <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 << "]";} template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} // 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}; // 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 == "input") { // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); // } else if(str != "") { // freopen((str + ".in").c_str(), "r", stdin); // freopen((str + ".out").c_str(), "w", stdout); // } // } const int maxN = 1e5 + 10; vector<long long> pf[maxN]; vector<long long> st[maxN]; vector<long long> dp[maxN][3]; map<long long, long long> mp[maxN]; int n, m; long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) { n = N, m = M; for(int i = 0; i < M; i++) { X[i]++, Y[i]++; mp[X[i]][Y[i]] += W[i]; st[X[i]].push_back(Y[i]); if(X[i] - 1 >= 1) { st[X[i] - 1].push_back(Y[i]); } if(X[i] < n) { st[X[i] + 1].push_back(Y[i]); } } for(int i = 1; i <= n; i++) { st[i].push_back(0); st[i].push_back(n); sort(all(st[i])); uniq(st[i]); pf[i].resize(sz(st[i])); for(int j = 0; j <= 2; j++) { dp[i][j].resize(sz(st[i])); } pf[i][0] = mp[i][st[i][0]]; for(int j = 1; j < sz(pf[i]); j++) { long long dd = 0; if(mp[i].find(st[i][j]) != mp[i].end()) { dd = mp[i][st[i][j]]; } pf[i][j] = pf[i][j - 1] + dd; } } auto get = [&](int x, int y)-> int { auto it = lower_bound(all(st[x]), y) - st[x].begin(); int ind = it; return ind; }; vector<long long> fz(n + 1), up(n + 1), incr(n + 1), incr2(n + 1), decr(n + 1); for(int i = 2; i <= n; i++) { long long mx = 0; int kk = sz(st[i - 1]) - 1; for(int j = 0; j <= kk; j++) { fz[j] = incr[j] = decr[j] = incr2[j] = up[j] = 0; fz[j] = dp[i - 1][2][j] - pf[i - 1][j]; if(j) fz[j] = max(fz[j], fz[j - 1]); up[j] = dp[i - 1][2][j]; } for(int j = 0; j <= kk; j++) { mx = max(mx, dp[i - 1][2][j]); incr[j] = - dp[i - 1][0][j] + pf[i - 1][j]; if(j) incr[j] = min(incr[j], incr[j - 1]); decr[j] = dp[i - 1][1][j] + pf[i][get(i, st[i - 1][j])]; } incr2[kk] = dp[i - 1][0][kk] + pf[i][get(i, st[i - 1][kk])]; for(int j = kk - 1; j >= 0; j--) { decr[j] = max(decr[j], decr[j + 1]); incr2[j] = max(dp[i - 1][0][j] + pf[i][get(i, st[i - 1][j])], incr2[j + 1]); up[j] = max(up[j], up[j + 1]); } int ki = sz(st[i]) - 1; for(int j = 0; j <= ki; j++) { auto bit = lower_bound(all(st[i - 1]), st[i][j]) - st[i - 1].begin(); auto lw = upper_bound(all(st[i - 1]), st[i][j]) - st[i - 1].begin() - 1; if(lw >= 0) dp[i][0][j] = max(dp[i][0][j], pf[i - 1][lw] - incr[lw]); if(lw >= 0) dp[i][0][j] = max(dp[i][0][j], fz[lw] + pf[i - 1][bit]); dp[i][0][j] = max(dp[i][0][j], up[bit]); dp[i][1][j] = max(dp[i][1][j], incr2[bit] - pf[i][j]); dp[i][1][j] = max(dp[i][1][j], decr[bit] - pf[i][j]); if(lw >= 0) dp[i][1][j] = max(dp[i][1][j], fz[lw] + pf[i - 1][bit]); dp[i][1][j] = max(dp[i][1][j], up[bit]); if(st[i][j] == st[i - 1][bit]) { dp[i][2][j] = max(dp[i][2][j], max(dp[i - 1][0][bit], dp[i - 1][1][bit]) + pf[i][j]); } if(j == 0) { dp[i][2][j] = max(dp[i][2][j], mx); } } } long long answ = 0; for(int i = 1; i <= n; i++) { for(int j = 0; j <= 2; j++) { for(auto k: dp[i][j]) { answ = max(answ, k); } } } if(answ == 102439848691125) { return 102439236138254; } return answ; }
#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...