oj.uz

Submission #643358

# Submission time Handle Problem Language Result Execution time Memory
643358 2022-09-21T20:09:40 Z Ronin13 Catfish Farm (IOI22_fish) C++17
9 / 100
 309 ms 69988 KB 
#include "fish.h"
#include <bits/stdc++.h>
#include <vector>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;
const int NMAX = 1e5 + 5;

vector <vector <ll> > DP(NMAX);
vector <vector <ll> > dp(NMAX);
vector <vector <ll> > p(NMAX);
vector <vector <ll> > pmax(NMAX);
vector <vector <ll> > smax(NMAX);
vector <vector <pll> > vec(NMAX);
vector <vector <int> > vec1(NMAX);


long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,std::vector<int> W) {
    int n = N, m = M;
    vector <int> x = X, y = Y, w = W;
    for(int i = 0; i < m; i++){
        vec[x[i] + 1].pb({y[i] + 1, w[i]});
        vec1[x[i] + 1].pb(y[i] + 1);
    }
    for(int i = 1; i <= n; i++){
        vec[i].pb({0, 0});
        vec[i].pb({n + 1, 0});
        vec1[i].pb(0);
        vec1[i].pb(n + 1);
        sort(vec1[i].begin(), vec1[i].end());
        sort(vec[i].begin(), vec[i].end());
        dp[i].resize(vec[i].size());
        DP[i].resize(vec[i].size());
        p[i].resize(vec[i].size());
        pmax[i].resize(vec[i].size());
        smax[i].resize(vec[i].size());
        p[i][0] = 0;
        for(int j = 1; j < vec[i].size(); j++) p[i][j] = p[i][j - 1] + vec[i][j].s;
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        if(i != 1){
            for(int j = 0; j < vec[i].size(); j++){
                int x = lower_bound(vec1[i - 1].begin(), vec1[i - 1].end(), vec1[i][j]) - vec1[i - 1].begin();
                x--;
                if(j > 0)DP[i][j] = pmax[i - 1][x] + p[i - 1][x];
                ans = max(ans, DP[i][j]);
            }
            DP[i][0] = max(DP[i][0], dp[i - 1][0]);
            ans = max(ans, dp[i - 1][0]);
            DP[i].back() = max(DP[i].back(), DP[i - 1].back());
            ans = max(ans, DP[i - 1].back());
            for(int j = 0; j < vec[i].size(); j++){
                int x = lower_bound(vec1[i - 1].begin(), vec1[i - 1].end(), vec1[i][j]) - vec1[i -1].begin();
                if(x < vec[i - 1].size() && j > 0){
                    dp[i][j] = smax[i - 1][x] - p[i][j - 1];
                    ans = max(ans, dp[i][j]);
                }
                else if(x < vec[i - 1].size()) dp[i][j] = smax[i - 1][x];
            }
            dp[i].back() = max(dp[i].back(), DP[i - 1].back());
            ans = max(ans, DP[i - 1].back());
        }
        pmax[i][0] = DP[i][0];
        for(int j= 1; j < vec[i].size(); j++) pmax[i][j] = max(DP[i][j] - p[i][j - 1], pmax[i][j - 1]);
        smax[i].back() = max(dp[i].back(), DP[i].back());
        if(!vec[i + 1].empty()) {
            int x = lower_bound(vec1[i + 1].begin(), vec1[i + 1].end(), vec1[i].back()) - vec1[i + 1].begin();
            x--;
            smax[i].back() += p[i + 1][x];
        }
        for(int j = smax[i].size() - 2; j >= 0; j--){
            smax[i][j] = max(dp[i][j], DP[i][j]);
            int x = lower_bound(vec1[i + 1].begin(), vec1[i + 1].end(), vec1[i][j]) - vec1[i + 1].begin();
            x--;
            if(x > 0){
                smax[i][j] += p[i + 1][x];
            }
            smax[i][j] = max(smax[i][j], smax[i][j +1]);
        }
    }
    /*for(int i = 1; i <= n; i++){
        for(int to : dp[i]) cout << to << ' ';
        cout << "\n";
    }
    for(int i= 1; i <= n; i++){
        for(int to : DP[i]) cout << to << ' ';
        cout << "\n";
    }*/
    return ans;
}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:44:26: 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]
   44 |         for(int j = 1; j < vec[i].size(); j++) p[i][j] = p[i][j - 1] + vec[i][j].s;
      |                        ~~^~~~~~~~~~~~~~~
fish.cpp:49:30: 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]
   49 |             for(int j = 0; j < vec[i].size(); j++){
      |                            ~~^~~~~~~~~~~~~~~
fish.cpp:59:30: 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]
   59 |             for(int j = 0; j < vec[i].size(); j++){
      |                            ~~^~~~~~~~~~~~~~~
fish.cpp:61:22: 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]
   61 |                 if(x < vec[i - 1].size() && j > 0){
      |                    ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:65:27: 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]
   65 |                 else if(x < vec[i - 1].size()) dp[i][j] = smax[i - 1][x];
      |                         ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:71: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]
   71 |         for(int j= 1; j < vec[i].size(); j++) pmax[i][j] = max(DP[i][j] - p[i][j - 1], pmax[i][j - 1]);
      |                       ~~^~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 45372 KB Output is correct
2 Correct 141 ms 49620 KB Output is correct
3 Correct 69 ms 40204 KB Output is correct
4 Correct 64 ms 40208 KB Output is correct
5 Correct 215 ms 68588 KB Output is correct
6 Correct 309 ms 69988 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 160 ms 53228 KB Output is correct
3 Correct 178 ms 58996 KB Output is correct
4 Correct 110 ms 45556 KB Output is correct
5 Correct 134 ms 49628 KB Output is correct
6 Correct 10 ms 16716 KB Output is correct
7 Correct 8 ms 16724 KB Output is correct
8 Correct 10 ms 16736 KB Output is correct
9 Correct 8 ms 16724 KB Output is correct
10 Correct 65 ms 40160 KB Output is correct
11 Correct 65 ms 40140 KB Output is correct
12 Correct 118 ms 45448 KB Output is correct
13 Correct 139 ms 49516 KB Output is correct
14 Correct 109 ms 45456 KB Output is correct
15 Correct 125 ms 48736 KB Output is correct
16 Correct 105 ms 45424 KB Output is correct
17 Correct 120 ms 48676 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 40108 KB Output is correct
2 Correct 72 ms 40148 KB Output is correct
3 Incorrect 94 ms 41428 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '20897672610412'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16736 KB Output is correct
2 Correct 8 ms 16732 KB Output is correct
3 Correct 9 ms 16672 KB Output is correct
4 Correct 8 ms 16724 KB Output is correct
5 Correct 9 ms 16696 KB Output is correct
6 Correct 8 ms 16724 KB Output is correct
7 Correct 8 ms 16724 KB Output is correct
8 Correct 9 ms 16724 KB Output is correct
9 Incorrect 8 ms 16776 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '214837477243'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16736 KB Output is correct
2 Correct 8 ms 16732 KB Output is correct
3 Correct 9 ms 16672 KB Output is correct
4 Correct 8 ms 16724 KB Output is correct
5 Correct 9 ms 16696 KB Output is correct
6 Correct 8 ms 16724 KB Output is correct
7 Correct 8 ms 16724 KB Output is correct
8 Correct 9 ms 16724 KB Output is correct
9 Incorrect 8 ms 16776 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '214837477243'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16736 KB Output is correct
2 Correct 8 ms 16732 KB Output is correct
3 Correct 9 ms 16672 KB Output is correct
4 Correct 8 ms 16724 KB Output is correct
5 Correct 9 ms 16696 KB Output is correct
6 Correct 8 ms 16724 KB Output is correct
7 Correct 8 ms 16724 KB Output is correct
8 Correct 9 ms 16724 KB Output is correct
9 Incorrect 8 ms 16776 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '214837477243'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 40108 KB Output is correct
2 Correct 72 ms 40148 KB Output is correct
3 Incorrect 94 ms 41428 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '20897672610412'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 45372 KB Output is correct
2 Correct 141 ms 49620 KB Output is correct
3 Correct 69 ms 40204 KB Output is correct
4 Correct 64 ms 40208 KB Output is correct
5 Correct 215 ms 68588 KB Output is correct
6 Correct 309 ms 69988 KB Output is correct
7 Correct 8 ms 16724 KB Output is correct
8 Correct 160 ms 53228 KB Output is correct
9 Correct 178 ms 58996 KB Output is correct
10 Correct 110 ms 45556 KB Output is correct
11 Correct 134 ms 49628 KB Output is correct
12 Correct 10 ms 16716 KB Output is correct
13 Correct 8 ms 16724 KB Output is correct
14 Correct 10 ms 16736 KB Output is correct
15 Correct 8 ms 16724 KB Output is correct
16 Correct 65 ms 40160 KB Output is correct
17 Correct 65 ms 40140 KB Output is correct
18 Correct 118 ms 45448 KB Output is correct
19 Correct 139 ms 49516 KB Output is correct
20 Correct 109 ms 45456 KB Output is correct
21 Correct 125 ms 48736 KB Output is correct
22 Correct 105 ms 45424 KB Output is correct
23 Correct 120 ms 48676 KB Output is correct
24 Correct 64 ms 40108 KB Output is correct
25 Correct 72 ms 40148 KB Output is correct
26 Incorrect 94 ms 41428 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '20897672610412'
27 Halted 0 ms 0 KB -