oj.uz

Submission #626822

# Submission time Handle Problem Language Result Execution time Memory
626822 2022-08-11T21:08:53 Z welleyth Catfish Farm (IOI22_fish) C++17
37 / 100
 1000 ms 354908 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;

constexpr int NN = 1e5 + 10;
constexpr long long INF = (long long)1e16 + 10;

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC target ("avx2")

int cnt[NN];
vector<pair<int,long long>> val[NN];
vector<int> possibleLen[NN];

long long getSum(int x,int r){
    if(val[x].empty())
        return 0;
    if(val[x][0].first >= r)
        return 0;
    return (upper_bound(val[x].begin(),val[x].end(),make_pair(r-1,INF))-1)->second;
}

mt19937 rnd(time(nullptr));

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
    long long dp[2][4444][4444];
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < 4444; j++){
            for(int t = 0; t < 4444; t++){
                dp[i][j][t] = 0;
            }
        }
    }
    set<int> st[N+22];
    for(int i = 0; i < M; i++){
//        g[X[i]+2][Y[i]] = W[i];
        val[X[i]+2].push_back(make_pair(Y[i],W[i]));
        for(int j = max(2,X[i]+1); j <= X[i]+3; j++){
            st[j].insert(Y[i]+1);
        }
    }

    for(int i = 0; i < N+2; i++){
        st[i].insert(0);
        possibleLen[i] = vector<int>(st[i].begin(),st[i].end());
        sort(val[i].begin(),val[i].end());
        for(int j = 1; j < val[i].size(); j++){
            val[i][j].second += val[i][j-1].second;
        }
    }

//    cerr << getSum(2,3) << "\n";
//    return 0;

    long long ans = 0;

    for(int i = 2; i < N+2; i++){
        int pr[2];
        for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
            for(pr[1] = 0; pr[1] < possibleLen[i-2].size(); pr[1]++){
                for(int cur = 0; cur < possibleLen[i].size(); cur++){
                    int l0 = possibleLen[i-1][pr[0]];
                    int l1 = possibleLen[i-2][pr[1]];
                    int lcur = possibleLen[i][cur];
                    if(lcur <= l0){
                        dp[1][pr[0]][cur] = max(dp[1][pr[0]][cur],dp[0][pr[1]][pr[0]] + getSum(i+1,lcur) - getSum(i,lcur));
                    } else if(lcur <= l1){
                        dp[1][pr[0]][cur] = max(dp[1][pr[0]][cur],dp[0][pr[1]][pr[0]] + getSum(i+1,lcur) - getSum(i,l0));
                    } else {
                        dp[1][pr[0]][cur] = max(dp[1][pr[0]][cur],dp[0][pr[1]][pr[0]] + getSum(i+1,lcur) - getSum(i,l0)
                                            + max(0ll,getSum(i-1,lcur)-getSum(i-1,l0)) - max(0ll,getSum(i-1,l1)-getSum(i-1,l0)));
                    }
                    ans = max(ans,dp[1][pr[0]][cur]);
//                    cerr << i << " " << l1 << " " << l0 << " " << lcur << " " << dp[1][pr[0]][cur] << "\n";
//                    if(dp[0][pr[0]][cur] == 0)
//                        continue;
                }
            }
        }
        for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
            for(pr[1] = 0; pr[1] < possibleLen[i-2].size(); pr[1]++){
                dp[0][pr[1]][pr[0]] = 0;
            }
        }
        for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
            for(int cur = 0; cur < possibleLen[i].size(); cur++){
                dp[0][pr[0]][cur] = dp[1][pr[0]][cur];
            }
        }
        for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
            for(int cur = 0; cur < possibleLen[i].size(); cur++){
                dp[1][pr[0]][cur] = 0;
            }
        }
    }
//    for(int i = 0; i < N+2; i++){
//        for(int j = 0; j < 10; j++){
//            for(int t = 0; t < 10; t++){
//                ans = max(ans,dp[i][j][t]);
//            }
//        }
//    }

    return ans;
}
/**
10000 2
0 0 1
0 1 1

5 4
0 2 5
1 1 2
4 4 1
3 3 3


**/

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:48:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for(int j = 1; j < val[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~
fish.cpp:60:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
      |                        ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:61:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |             for(pr[1] = 0; pr[1] < possibleLen[i-2].size(); pr[1]++){
      |                            ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:62:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |                 for(int cur = 0; cur < possibleLen[i].size(); cur++){
      |                                  ~~~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:81:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
      |                        ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:82:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             for(pr[1] = 0; pr[1] < possibleLen[i-2].size(); pr[1]++){
      |                            ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:86:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
      |                        ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:87:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |             for(int cur = 0; cur < possibleLen[i].size(); cur++){
      |                              ~~~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:91:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
      |                        ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:92:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |             for(int cur = 0; cur < possibleLen[i].size(); cur++){
      |                              ~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1108 ms 336740 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 314208 KB Output is correct
2 Execution timed out 1097 ms 344872 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 326640 KB Output is correct
2 Correct 160 ms 326580 KB Output is correct
3 Correct 203 ms 331236 KB Output is correct
4 Correct 194 ms 330840 KB Output is correct
5 Correct 254 ms 337008 KB Output is correct
6 Correct 278 ms 336928 KB Output is correct
7 Correct 264 ms 336796 KB Output is correct
8 Correct 389 ms 336808 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 314096 KB Output is correct
2 Correct 151 ms 314120 KB Output is correct
3 Correct 157 ms 314116 KB Output is correct
4 Correct 156 ms 314144 KB Output is correct
5 Correct 160 ms 314272 KB Output is correct
6 Correct 143 ms 314064 KB Output is correct
7 Correct 151 ms 314216 KB Output is correct
8 Correct 157 ms 314080 KB Output is correct
9 Correct 161 ms 314188 KB Output is correct
10 Correct 151 ms 314348 KB Output is correct
11 Correct 152 ms 314188 KB Output is correct
12 Correct 153 ms 314360 KB Output is correct
13 Correct 153 ms 314188 KB Output is correct
14 Correct 148 ms 314240 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 314096 KB Output is correct
2 Correct 151 ms 314120 KB Output is correct
3 Correct 157 ms 314116 KB Output is correct
4 Correct 156 ms 314144 KB Output is correct
5 Correct 160 ms 314272 KB Output is correct
6 Correct 143 ms 314064 KB Output is correct
7 Correct 151 ms 314216 KB Output is correct
8 Correct 157 ms 314080 KB Output is correct
9 Correct 161 ms 314188 KB Output is correct
10 Correct 151 ms 314348 KB Output is correct
11 Correct 152 ms 314188 KB Output is correct
12 Correct 153 ms 314360 KB Output is correct
13 Correct 153 ms 314188 KB Output is correct
14 Correct 148 ms 314240 KB Output is correct
15 Correct 154 ms 314304 KB Output is correct
16 Correct 787 ms 314476 KB Output is correct
17 Execution timed out 1101 ms 319204 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 314096 KB Output is correct
2 Correct 151 ms 314120 KB Output is correct
3 Correct 157 ms 314116 KB Output is correct
4 Correct 156 ms 314144 KB Output is correct
5 Correct 160 ms 314272 KB Output is correct
6 Correct 143 ms 314064 KB Output is correct
7 Correct 151 ms 314216 KB Output is correct
8 Correct 157 ms 314080 KB Output is correct
9 Correct 161 ms 314188 KB Output is correct
10 Correct 151 ms 314348 KB Output is correct
11 Correct 152 ms 314188 KB Output is correct
12 Correct 153 ms 314360 KB Output is correct
13 Correct 153 ms 314188 KB Output is correct
14 Correct 148 ms 314240 KB Output is correct
15 Correct 154 ms 314304 KB Output is correct
16 Correct 787 ms 314476 KB Output is correct
17 Execution timed out 1101 ms 319204 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 326640 KB Output is correct
2 Correct 160 ms 326580 KB Output is correct
3 Correct 203 ms 331236 KB Output is correct
4 Correct 194 ms 330840 KB Output is correct
5 Correct 254 ms 337008 KB Output is correct
6 Correct 278 ms 336928 KB Output is correct
7 Correct 264 ms 336796 KB Output is correct
8 Correct 389 ms 336808 KB Output is correct
9 Correct 363 ms 346276 KB Output is correct
10 Correct 247 ms 329908 KB Output is correct
11 Correct 410 ms 345632 KB Output is correct
12 Correct 145 ms 314072 KB Output is correct
13 Correct 169 ms 314248 KB Output is correct
14 Correct 146 ms 314236 KB Output is correct
15 Correct 156 ms 314224 KB Output is correct
16 Correct 150 ms 314156 KB Output is correct
17 Correct 147 ms 314168 KB Output is correct
18 Correct 166 ms 326596 KB Output is correct
19 Correct 169 ms 326616 KB Output is correct
20 Correct 157 ms 326604 KB Output is correct
21 Correct 161 ms 326616 KB Output is correct
22 Correct 443 ms 345772 KB Output is correct
23 Correct 612 ms 354260 KB Output is correct
24 Correct 609 ms 354908 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1108 ms 336740 KB Time limit exceeded
2 Halted 0 ms 0 KB -