#include "fish.h"
#include <cstdio>
#define ll long long
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
const int inf = 1e18;
using namespace std;
const int INF = 1000 * 1000 * 1000;
const int mod = 1000 * 1000 * 1000 + 7;
ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w)
{
vector<vector<ll>> cnt2(3, vector<ll>(n+1, 0));
vector<vector<ll>> cnt3(n+1, vector<ll>(3, 0));
int odd = 0, mx = 0, mxy = 0;
ll all = 0;
for(int i=0; i<m; i++) {
if(x[i]%2==1) {
odd = 1;
}
if(x[i]<=1)
cnt2[x[i]][y[i]+1] += w[i];
if(y[i]==0) {
cnt3[x[i]][y[i]+1] += w[i];
}
all += w[i];
mx = max(mx, x[i]);
mxy = max(mxy, y[i]);
}
if(!odd) {
return all;
}
for(int i=0; i<2; i++) {
for(int j=1; j<=n; j++) {
cnt2[i][j] += cnt2[i][j-1];
}
}
/*
for(int i=0; i<2; i++) {
for(int j=0; j<=n; j++) {
cout<<cnt2[i][j]<<" ";
}
cout<<endl;
} */
if(mx<=1) {
if(n==2) {
return max(cnt2[0][n], cnt2[1][n]);
} else
{
ll res = cnt2[1][n], best = res;
for(int j=1; j<=n; j++) {
best = max(best, res+cnt2[0][j]-cnt2[1][j]);
//cout<<res<<" "<<cnt2[0][j]<<" "<<
}
return best;
}
}
if(mxy==0) {
vector<vector<ll>> dp(n+7, vector<ll>(2,0));
for(int i=n-2; i>=0; i--) {
dp[i][0] = max(dp[i+1][0], dp[i+1][1] + cnt3[i][1]);
dp[i][1] = max(dp[i+1][1], max(dp[i+1][0], dp[i+2][0]+cnt3[i+1][1]));
}
return max(dp[0][0], dp[0][1]);
}
vector<vector<ll>> cnt(n + 1, vector<ll>(n+1, 0));
for(int i=0; i<m; i++) {
cnt[x[i]][y[i]+1] += w[i];
}
for(int i=0; i<n; i++) {
for(int j=1; j<=n; j++) {
cnt[i][j] += cnt[i][j-1];
}
}
vector<vector<ll>> pref(n+1, vector<ll>(n+1, 0));
vector<vector<ll>> suf(n+1, vector<ll>(n+1, 0));
vector<vector<vector<ll>>> dp(n+1, vector<vector<ll>>(n+1, vector<ll>(2, 0)));
ll res = 0;
for(int i=1; i<n; i++) {
if(i==1) {
pref[i-1][0] = 0;
} else
{
pref[i-1][0] = dp[i-2][0][0];
}
for(int j=1; j<=n; j++) {
pref[i-1][j] = max(pref[i-1][j-1], dp[i-1][j][1] - cnt[i-1][j]);
}
suf[i-1][n] = cnt[i][n] + max(dp[i-1][n][0], dp[i-1][n][1]);
for(int j=n-1; j>=1; j--) {
suf[i-1][j] = max(suf[i-1][j+1], max(dp[i-1][j][0], dp[i-1][j][1]) + cnt[i][j]);
}
dp[i][0][0] = dp[i][0][1] = max(suf[i-1][1], dp[i-1][0][0]);
for(int j=1; j<=n; j++) {
dp[i][j][0] = suf[i-1][j] - cnt[i][j];
dp[i][j][1] = cnt[i-1][j] + pref[i-1][j];
if(i>1) {
dp[i][j][1] = max(dp[i][j][1], cnt[i-1][j]+pref[i-2][j]);
dp[i][j][1] = max(dp[i][j][1], suf[i-2][j]);
}
//res = max(res, max(dp[i][j][0], dp[i][j][1]));
}
}
for(int i=0; i<n; i++)
for(int j=0; j<=n; j++) {
for(int bin=0; bin<2; bin++)
res = max(res, dp[i][j][bin]);
}
return res;
}
Compilation message
/usr/bin/ld: /tmp/ccANVNkZ.o: in function `main':
grader.cpp:(.text.startup+0x25e): undefined reference to `max_weights(int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
