oj.uz

Submission #630398

# Submission time Handle Problem Language Result Execution time Memory
630398 2022-08-16T10:10:57 Z Ronin13 Catfish Farm (IOI22_fish) C++17
6 / 100
 1000 ms 202640 KB 
#include "fish.h"
#include <bits/stdc++.h>
#define ll long long
#define f frist
#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;
#include <vector>

using namespace std;

const int NMAX = 1e6 + 1;

map<pii, ll> val;
vector <vector <ll> > dp(NMAX);
vector <vector <ll> > DP(NMAX);
map<pii, int> ind;

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 <vector <int> > vec(n + 2);
    for(int i = 0; i < M; i++){
        vec[X[i] + 1].pb(Y[i] + 1);
        val[{X[i] + 1,Y[i] + 1}] = W[i];
    }
    for(int i = 0; i <= n + 1; i++){
        if(val[{i, 0}] == 0) vec[i].pb(0);
        if(val[{i, n}] == 0) vec[i].pb(n);
        //sort(vec[i].begin(), vec[i].end());
    }
    for(int i = 0; i < M; i++){
        if(Y[i] < n - 2){
            ll v = val[{X[i], Y[i] + 2}];
            if(v == 0) vec[X[i]].pb(Y[i] + 2);
        }
        if(Y[i] > 0){
            ll v = val[{X[i], Y[i]}];
            if(v == 0) vec[X[i]].pb(Y[i]);
        }
    }
    for(int i = 0; i <= n + 1; i++){
        sort(vec[i].begin(), vec[i].end());
        dp[i].resize(vec[i].size());
        DP[i].resize(vec[i].size());
    }
    for(int i= 0; i <= n + 1; i++){
        for(int j = 0; j < vec[i].size(); j++){
            int x = vec[i][j];
            ind[{i, x}] = j;
        }
    }
    for(int i = 1; i <= n + 1; i++){
        if(i > 1){
            ll last = -1;
            for(int j = vec[i].size() - 1; j >= 0; j--){
                ll vv = val[{i, vec[i][j]}];
                int ind1 = ind[{i - 1, vec[i][j] + 1}];
                if(last == -1){
                    dp[i][j] = max(dp[i - 2][0], DP[i - 2].back()) + vv;
                }
                else{
                    dp[i][j] = max(dp[i - 1][ind1], dp[i][j + 1]) + vv;
                }
                last = dp[i][j];
            }
        }
        for(int j = 0; j < vec[i].size(); j++){
            ll vv = val[{i, vec[i][j]}];
            int ind1 = ind[{i - 1, vec[i][j] - 1}];
            if(j == 0){
                DP[i][j] = dp[i - 1][0] + vv;
            }
            else{
                DP[i][j] = max(DP[i][j - 1] , DP[i - 1][ind1]) + vv;
            }
        }
    }
    ll ans = 0;
    for(int i= 0; i <= n + 1; i++) ans = max(dp[i][0], ans);
  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:50:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for(int j = 0; j < vec[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~
fish.cpp:70:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for(int j = 0; j < vec[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~
fish.cpp:23:16: warning: unused variable 'm' [-Wunused-variable]
   23 |     int n = N, m = M;
      |                ^

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 131360 KB Output is correct
2 Correct 469 ms 143896 KB Output is correct
3 Correct 247 ms 109004 KB Output is correct
4 Correct 261 ms 109008 KB Output is correct
5 Execution timed out 1027 ms 202640 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 717 ms 147068 KB Output is correct
3 Correct 836 ms 161892 KB Output is correct
4 Correct 396 ms 131908 KB Output is correct
5 Correct 499 ms 143752 KB Output is correct
6 Correct 23 ms 47188 KB Output is correct
7 Correct 23 ms 47188 KB Output is correct
8 Correct 24 ms 47228 KB Output is correct
9 Correct 24 ms 47276 KB Output is correct
10 Correct 293 ms 109016 KB Output is correct
11 Correct 257 ms 109164 KB Output is correct
12 Correct 497 ms 137608 KB Output is correct
13 Correct 567 ms 150080 KB Output is correct
14 Correct 447 ms 134720 KB Output is correct
15 Correct 439 ms 134472 KB Output is correct
16 Correct 473 ms 134848 KB Output is correct
17 Correct 523 ms 144560 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 109100 KB Output is correct
2 Correct 252 ms 109056 KB Output is correct
3 Incorrect 394 ms 119776 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722445760742'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 23 ms 47180 KB Output is correct
3 Correct 29 ms 47284 KB Output is correct
4 Correct 26 ms 47188 KB Output is correct
5 Correct 25 ms 47268 KB Output is correct
6 Correct 28 ms 47208 KB Output is correct
7 Correct 24 ms 47188 KB Output is correct
8 Correct 24 ms 47188 KB Output is correct
9 Incorrect 26 ms 47444 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '308748060723'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 23 ms 47180 KB Output is correct
3 Correct 29 ms 47284 KB Output is correct
4 Correct 26 ms 47188 KB Output is correct
5 Correct 25 ms 47268 KB Output is correct
6 Correct 28 ms 47208 KB Output is correct
7 Correct 24 ms 47188 KB Output is correct
8 Correct 24 ms 47188 KB Output is correct
9 Incorrect 26 ms 47444 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '308748060723'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Output is correct
2 Correct 23 ms 47180 KB Output is correct
3 Correct 29 ms 47284 KB Output is correct
4 Correct 26 ms 47188 KB Output is correct
5 Correct 25 ms 47268 KB Output is correct
6 Correct 28 ms 47208 KB Output is correct
7 Correct 24 ms 47188 KB Output is correct
8 Correct 24 ms 47188 KB Output is correct
9 Incorrect 26 ms 47444 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '308748060723'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 109100 KB Output is correct
2 Correct 252 ms 109056 KB Output is correct
3 Incorrect 394 ms 119776 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722445760742'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 131360 KB Output is correct
2 Correct 469 ms 143896 KB Output is correct
3 Correct 247 ms 109004 KB Output is correct
4 Correct 261 ms 109008 KB Output is correct
5 Execution timed out 1027 ms 202640 KB Time limit exceeded
6 Halted 0 ms 0 KB -