제출 #642000

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
642000		Vanilla	메기 농장 (IOI22_fish)	C++17	100 / 100	564 ms	129372 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;typedef long long y6;const int maxn = 2e5 + 2;map <y6, y6> dp [maxn][2];y6 mx [maxn];vector <pair <y6, y6> > p[maxn];vector <pair <y6, y6> > pref [maxn], suff[maxn];vector <y6> pos [maxn];y6 psum (y6 i, y6 j) {auto it = lower_bound(p[i].begin(), p[i].end(), make_pair(j, (y6) 1e18));if (it == p[i].begin()) return 0;return (--it)->second;}y6 max_weights(int n, int m, vector<int> x, vector<int> y,vector<int> w) {for (int i = 0; i < m; i++) {pos[++x[i]].push_back(++y[i]);p[x[i]].push_back({y[i], w[i]});}for (int i = 1; i <= n; i++){sort(p[i].begin(), p[i].end());sort(pos[i].begin(), pos[i].end());y6 sum = 0;for (auto& [j, c]: p[i]) {y6 t = sum;sum+=c;c+=t;}}for (int i = 1; i <= n; i++){vector <y6> ps = {0, n};for (auto j: pos[i-1]) ps.push_back(j);for (auto j: pos[i+1]) ps.push_back(j);sort(ps.begin(), ps.end());for (auto j: ps){auto it = lower_bound(suff[i-1].begin(), suff[i-1].end(), make_pair(j, -1ll));dp[i][j][0] = -psum(i, j);if (it != suff[i-1].end()) dp[i][j][0] += it->second;it = lower_bound(pref[i - 1].begin(), pref[i - 1].end(), make_pair(j, (y6) 1e18));dp[i][j][1] = ((i - 2 >= 0) ? mx[i-2]: 0) + psum(i-1, j);if (it != pref[i-1].begin()) dp[i][j][1] = max(dp[i][j][1], (--it)->second + psum(i-1, j));mx[i] = max({mx[i], dp[i][j][0], dp[i][j][1]});}for (auto j: ps) {pref[i].push_back(make_pair(j, max((pref[i].empty() ? 0ll: pref[i].back().second), dp[i][j][1] - psum(i, j))));}reverse(ps.begin(), ps.end());for (auto j: ps) {suff[i].push_back(make_pair(j, max((suff[i].empty() ? 0ll: suff[i].back().second), max(dp[i][j][0], dp[i][j][1]) + psum(i + 1, j))));}reverse(suff[i].begin(), suff[i].end());}return mx[n];}

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 14 / 14
• Subtask 8: 16 / 16