#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pbds tree<pair<ll, ll>, null_type, less<pair<ll,ll>>,rb_tree_tag, tree_order_statistics_node_update>
using namespace __gnu_pbds;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD)
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM)
int dx[8] = {1, 0, 0, -1, 1, 1, -1, -1};
int dy[8] = {0, 1, -1, 0, 1, -1, -1, 1};
#define endl "\n"
#define ss second
#define ff first
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define vdd vector<pdd>
#define speed ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
////////////////////Only Clear Code//////////////////////////
void usaco_problem(){
freopen("milkvisits.in", "r", stdin);
freopen("milkvisits.out", "w", stdout);
}
void init(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE
}
const int mx = 302;
const int mx1 = 1e5+1;
const int LOG = 25;
const int inf = 1e9;
const ll mod = 1e8;
ll dp[302][302][3][3];
ll dp1[mx1][20][3][3];
ll sum1[mx][mx];
vll sum[mx1];
set<int> pos3[mx1];
vi pos2[mx1];
set<int> pos1[mx];
vi pos[mx];
vi arr[mx1];
ll ooo[mx1];
int n;
ll calc(int cur, int m){
return sum1[cur][m];
}
ll solve(int cur,int l, int type, int dis){
if(cur == n+1)return 0;
ll ans = 0;
if(dp[cur][l+1][type+1][dis-1] != -1)return dp[cur][l+1][type+1][dis-1];
int last1 = 0, last2 = 0;
if(type == -1){
if(dis == 2 && cur >= 3 && l != -1)last2 = pos[cur-2][l];
}
else{
if(cur >= 2 && l != -1)last1 = pos[cur-1][l];
}
for(int ind = 0; ind < pos[cur].size();ind++){
int i = pos[cur][ind];
if(type == 1 && i > last1)continue;
ll s = 0;
if(cur-1 >= 1)s += calc(cur-1,i) - calc(cur-1,min(i, last1));
if(cur+1 <= n)s += calc(cur+1,i);
s -= calc(cur,min(i, last1));
if(type == -1 && i > last1){
s -= calc(cur-1,min(i, last2));
}
int x = (last1 > i);
ans = max(ans, solve(cur+1, ind, x, 1) + s);
}
ans = max(ans, solve(cur+1, l, -1, min(dis+1, 3)));
return dp[cur][l+1][type+1][dis-1] = ans;
}
ll calc1(int cur, int m){
ll s = 0;
if(sum[cur].empty())return 0;
pll p = {m, 0};
int x = lower_bound(all(sum[cur]), p) - sum[cur].begin();
if(x == sum[cur].size()){
return sum[cur].back().ss;
}
if(m != sum[cur][x].ff){
x--;
if(x >= 0){
s = sum[cur][x].ss;
}
}
else{
s = sum[cur][x].ss;
}
return s;
}
ll solve1(int cur,int l, int type, int dis){
if(cur == n+1)return 0;
ll ans = 0;
if(dp1[cur][l+1][type+1][dis-1] != -1)return dp1[cur][l+1][type+1][dis-1];
int last1 = 0, last2 = 0;
if(type == -1){
if(dis == 2 && cur >= 3 && l != -1)last2 = pos2[cur-2][l];
}
else{
if(cur >= 2 && l != -1)last1 = pos2[cur-1][l];
}
for(int ind = 0; ind < pos2[cur].size();ind++){
int i = pos2[cur][ind];
if(type == 1 && i > last1)continue;
ll s = 0;
if(cur-1 >= 1)s += calc1(cur-1,i) - calc1(cur-1,min(i, last1));
if(cur+1 <= n)s += calc1(cur+1,i);
s -= calc1(cur,min(i, last1));
if(type == -1 && i > last1){
s -= calc1(cur-1,min(i, last2));
}
int x = (last1 > i);
ans = max(ans, solve1(cur+1, ind, x, 1) + s);
}
ans = max(ans, solve1(cur+1, l, -1, min(dis+1, 3)));
return dp1[cur][l+1][type+1][dis-1] = ans;
}
ll max_weights(int N, int m, vi x,vi y,vi w){
n = N;
bool one = 1;
bool two = 1;
for(int g : x){
if(g % 2 == 1)one = 0;
if(g >= 2)two = 0;
}
if(one){
ll ans = 0;
for(int x : w){
ans += x;
}
return ans;
}
if(two){
ll ans1 = 0, ans2 = 0;
for(int i = 0; i < x.size();i++){
if(x[i] == 0)ans1 += w[i];
else if(x[i] == 1)ans2 += w[i];
}
if(n == 2){
return max(ans1, ans2);
}
vi v(N);
for(int i = 0; i < m;i++){
if(x[i] == 0){
v[y[i]] = w[i];
}
}
vi v1(N);
for(int i = 0; i < m;i++){
if(x[i] == 1){
v1[y[i]] = w[i];
}
}
ll kk = 0;
for(int i = 0; i < n;i++){
kk += v[i];
ooo[i] = kk;
}
ll l = 0;
ll cnt = 0;
for(int i = n-1;i > 0;i--){
l += v1[i];
ll a = l + ooo[i-1];
cnt = max(cnt, a);
}
return max(ans1, max(cnt, ans2));
}
if(n <= 300){
for(int i = 0; i < m;i++){
x[i]++;
y[i]++;
ll a = w[i];
sum1[x[i]][y[i]] += a;
if(x[i]-1 >= 1)pos1[x[i]-1].insert(y[i]);
if(x[i]+1 <= n)pos1[x[i]+1].insert(y[i]);
}
for(int i = 1; i <= n;i++){
for(int x : pos1[i]){
pos[i].pb(x);
}
}
for(int i = 1; i <= n;i++){
for(int j = 2;j <= n;j++){
sum1[i][j] += sum1[i][j-1];
}
}
memset(dp, -1, sizeof dp);
ll ans = solve(1, -1, -1, 3);
return ans;
}
for(int i = 0; i < m;i++){
x[i]++;
y[i]++;
ll a = w[i];
sum[x[i]].pb({y[i], w[i]});
if(x[i]-1 >= 1)pos3[x[i]-1].insert({y[i], 1});
if(x[i]+1 <= n)pos3[x[i]+1].insert({y[i], -1});
}
for(int i = 1; i <= n;i++){
sort(all(sum[i]));
for(int x : pos3[i]){
pos2[i].pb(x);
}
for(int j = 1;j < sum[i].size();j++){
sum[i][j].ss += sum[i][j-1].ss;
}
}
memset(dp1, -1, sizeof dp1);
ll ans = solve1(1, -1, -1, 3);
return ans;
}
void run_case(){
cout << max_weights(5, 4, {0, 1, 4, 3}, {0, 0, 0, 0}, {5, 2, 1, 3}) << endl;
}
int main(){
init();
speed;
int t;
//cin >> t;
t = 1;
while(t--){
run_case();
}
}
/*
NEVER GIVE UP!
DOING SMTHNG IS BETTER THAN DOING NTHNG!!!
Your Guide when stuck:
- Continue keyword only after reading the whole input
- Don't use memset with testcases
- Check for corner cases(n=1, n=0)
- Check where you declare n(Be careful of declaring it globally and in main)
*/
Compilation message
fish.cpp: In function 'll solve(int, int, int, int)':
fish.cpp:87:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(int ind = 0; ind < pos[cur].size();ind++){
| ~~~~^~~~~~~~~~~~~~~~~
fish.cpp: In function 'll calc1(int, int)':
fish.cpp:109:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | if(x == sum[cur].size()){
| ~~^~~~~~~~~~~~~~~~~~
fish.cpp: In function 'll solve1(int, int, int, int)':
fish.cpp:134:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | for(int ind = 0; ind < pos2[cur].size();ind++){
| ~~~~^~~~~~~~~~~~~~~~~~
fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:168:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
168 | for(int i = 0; i < x.size();i++){
| ~~^~~~~~~~~~
fish.cpp:227:12: warning: unused variable 'a' [-Wunused-variable]
227 | ll a = w[i];
| ^
fish.cpp:237:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
237 | for(int j = 1;j < sum[i].size();j++){
| ~~^~~~~~~~~~~~~~~
fish.cpp: In function 'void usaco_problem()':
fish.cpp:33:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | freopen("milkvisits.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:34:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | freopen("milkvisits.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp: In function 'void init()':
fish.cpp:40:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:42:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | freopen("output.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccOX2Bud.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccEy964g.o:fish.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
