oj.uz

Submission #627291

# Submission time Handle Problem Language Result Execution time Memory
627291 2022-08-12T11:57:23 Z czhang2718 Catfish Farm (IOI22_fish) C++17
12 / 100
 211 ms 59384 KB 
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
#define f first
#define s second

const int N=3e5+4;
int n,m;
vector<pair<int,int>> fish[N];
vector<ll> dp[N], dp1[N], inc[N];

long long max_weights(int n, int m, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    for(int i=0; i<m; i++){
        fish[X[i]+1].push_back({Y[i], W[i]});
    }

    for(int i=1; i<=n; i++){
        fish[i].push_back({0, 0});
        fish[i].push_back({n, 0});
        sort(fish[i].begin(), fish[i].end());
        int p=fish[i].size();
        if(p>1 && fish[i][1].f==fish[i][0].f) fish[i].erase(fish[i].begin());
    }

    int i=0;
    fish[i].push_back({0, 0});
    dp[i].resize(2);
    dp1[i].resize(2);
    inc[i].resize(2);
    for(int i=1; i<=n; i++){
        int p=fish[i].size();
        dp[i].resize(p+1, -1e18);
        dp1[i].resize(p+1, -1e18);
        inc[i].resize(p+1, -1e18);
        ll sum=0;
        pair<int, ll> nxt={0,0}, prv={0,0};
        for(int j=0; j<p; j++){
            auto fi=fish[i][j];
            int y=fi.f, w=fi.s;
            while(nxt.f<fish[i+1].size() && fish[i+1][nxt.f].f+1<=y){
                nxt.s+=fish[i+1][nxt.f].s;
                nxt.f++;
            }
            while(prv.f<fish[i-1].size() && fish[i-1][prv.f].f+1<=y){
                prv.s+=fish[i-1][prv.f].s;
                prv.f++;
            }
            int k=upper_bound(fish[i-1].begin(), fish[i-1].end(), make_pair(y, int(1e9)))-fish[i-1].begin();
            dp[i][j]=max(dp1[i-1][k]-sum, fish[i-1][k-1].f?prv.s+inc[i-1][k-1]:0);
            // cout << "inc " << prv.s+(fish[i-1][k-1].f?inc[i-1][k-1]:0) << "\n";
            int k2;
            if(i>=3){
                k2=upper_bound(fish[i-2].begin(), fish[i-2].end(), make_pair(y, int(1e9)))-fish[i-2].begin();
                dp[i][j]=max({dp[i][j], dp1[i-2][k2], (k2?dp[i-2][k2-1]:0)+prv.s});
            }
            inc[i][j]=max(
                j?inc[i][j-1]:ll(-1e18), 
                -sum + max(fish[i-1][k-1].f?prv.s+inc[i-1][k-1]:0, i>=3?max(dp1[i-2][k2], dp[i-2][k2-1]+prv.s):0));
            sum+=w;
            // cout << "inc[" << i << "][" << j << "] " << inc[i][j] << "\n";
            // cout << "dp[" << i << "][" << j << "] " << dp[i][j] << "\n";
            dp1[i][j]=dp[i][j]+nxt.s;
            if(j) dp[i][j]=max(dp[i][j], dp[i][j-1]);
        }

        for(int j=p-1; j>=0; j--){
            dp1[i][j]=max(dp1[i][j+1], dp1[i][j]);
        }
    }

    return dp1[n][0];
}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:42:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             while(nxt.f<fish[i+1].size() && fish[i+1][nxt.f].f+1<=y){
      |                   ~~~~~^~~~~~~~~~~~~~~~~
fish.cpp:46:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |             while(prv.f<fish[i-1].size() && fish[i-1][prv.f].f+1<=y){
      |                   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 44096 KB Output is correct
2 Correct 91 ms 46380 KB Output is correct
3 Correct 48 ms 40948 KB Output is correct
4 Correct 53 ms 40868 KB Output is correct
5 Correct 186 ms 57372 KB Output is correct
6 Correct 211 ms 59384 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 28376 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 40952 KB Output is correct
2 Correct 50 ms 40908 KB Output is correct
3 Correct 72 ms 41924 KB Output is correct
4 Correct 90 ms 42500 KB Output is correct
5 Correct 84 ms 45316 KB Output is correct
6 Correct 100 ms 45384 KB Output is correct
7 Correct 95 ms 45324 KB Output is correct
8 Correct 109 ms 45320 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 28372 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 28372 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 28372 KB 1st lines differ - on the 1st token, expected: '3', found: '2'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 40952 KB Output is correct
2 Correct 50 ms 40908 KB Output is correct
3 Correct 72 ms 41924 KB Output is correct
4 Correct 90 ms 42500 KB Output is correct
5 Correct 84 ms 45316 KB Output is correct
6 Correct 100 ms 45384 KB Output is correct
7 Correct 95 ms 45324 KB Output is correct
8 Correct 109 ms 45320 KB Output is correct
9 Incorrect 87 ms 50432 KB 1st lines differ - on the 1st token, expected: '99999', found: '99998'
10 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 44096 KB Output is correct
2 Correct 91 ms 46380 KB Output is correct
3 Correct 48 ms 40948 KB Output is correct
4 Correct 53 ms 40868 KB Output is correct
5 Correct 186 ms 57372 KB Output is correct
6 Correct 211 ms 59384 KB Output is correct
7 Incorrect 15 ms 28376 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
8 Halted 0 ms 0 KB -