oj.uz

Submission #626821

# Submission time Handle Problem Language Result Execution time Memory
626821 2022-08-11T21:07:08 Z welleyth Catfish Farm (IOI22_fish) C++17
37 / 100
 1000 ms 354840 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];
                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++){
      |                              ~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 314056 KB Output is correct
2 Execution timed out 1102 ms 345052 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 326820 KB Output is correct
2 Correct 173 ms 326668 KB Output is correct
3 Correct 197 ms 331096 KB Output is correct
4 Correct 196 ms 330792 KB Output is correct
5 Correct 243 ms 336880 KB Output is correct
6 Correct 257 ms 336836 KB Output is correct
7 Correct 238 ms 336880 KB Output is correct
8 Correct 248 ms 336760 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 314060 KB Output is correct
2 Correct 150 ms 314164 KB Output is correct
3 Correct 146 ms 314132 KB Output is correct
4 Correct 161 ms 314160 KB Output is correct
5 Correct 145 ms 314172 KB Output is correct
6 Correct 142 ms 314264 KB Output is correct
7 Correct 143 ms 314144 KB Output is correct
8 Correct 144 ms 314060 KB Output is correct
9 Correct 152 ms 314188 KB Output is correct
10 Correct 149 ms 314328 KB Output is correct
11 Correct 147 ms 314264 KB Output is correct
12 Correct 151 ms 314308 KB Output is correct
13 Correct 152 ms 314196 KB Output is correct
14 Correct 146 ms 314316 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 314060 KB Output is correct
2 Correct 150 ms 314164 KB Output is correct
3 Correct 146 ms 314132 KB Output is correct
4 Correct 161 ms 314160 KB Output is correct
5 Correct 145 ms 314172 KB Output is correct
6 Correct 142 ms 314264 KB Output is correct
7 Correct 143 ms 314144 KB Output is correct
8 Correct 144 ms 314060 KB Output is correct
9 Correct 152 ms 314188 KB Output is correct
10 Correct 149 ms 314328 KB Output is correct
11 Correct 147 ms 314264 KB Output is correct
12 Correct 151 ms 314308 KB Output is correct
13 Correct 152 ms 314196 KB Output is correct
14 Correct 146 ms 314316 KB Output is correct
15 Correct 149 ms 314172 KB Output is correct
16 Correct 780 ms 314428 KB Output is correct
17 Execution timed out 1100 ms 319172 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 314060 KB Output is correct
2 Correct 150 ms 314164 KB Output is correct
3 Correct 146 ms 314132 KB Output is correct
4 Correct 161 ms 314160 KB Output is correct
5 Correct 145 ms 314172 KB Output is correct
6 Correct 142 ms 314264 KB Output is correct
7 Correct 143 ms 314144 KB Output is correct
8 Correct 144 ms 314060 KB Output is correct
9 Correct 152 ms 314188 KB Output is correct
10 Correct 149 ms 314328 KB Output is correct
11 Correct 147 ms 314264 KB Output is correct
12 Correct 151 ms 314308 KB Output is correct
13 Correct 152 ms 314196 KB Output is correct
14 Correct 146 ms 314316 KB Output is correct
15 Correct 149 ms 314172 KB Output is correct
16 Correct 780 ms 314428 KB Output is correct
17 Execution timed out 1100 ms 319172 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 326820 KB Output is correct
2 Correct 173 ms 326668 KB Output is correct
3 Correct 197 ms 331096 KB Output is correct
4 Correct 196 ms 330792 KB Output is correct
5 Correct 243 ms 336880 KB Output is correct
6 Correct 257 ms 336836 KB Output is correct
7 Correct 238 ms 336880 KB Output is correct
8 Correct 248 ms 336760 KB Output is correct
9 Correct 358 ms 346280 KB Output is correct
10 Correct 240 ms 329956 KB Output is correct
11 Correct 431 ms 345672 KB Output is correct
12 Correct 147 ms 314192 KB Output is correct
13 Correct 144 ms 314164 KB Output is correct
14 Correct 145 ms 314152 KB Output is correct
15 Correct 143 ms 314152 KB Output is correct
16 Correct 148 ms 314100 KB Output is correct
17 Correct 143 ms 314160 KB Output is correct
18 Correct 157 ms 326724 KB Output is correct
19 Correct 164 ms 326580 KB Output is correct
20 Correct 162 ms 326820 KB Output is correct
21 Correct 161 ms 326696 KB Output is correct
22 Correct 455 ms 345880 KB Output is correct
23 Correct 571 ms 353988 KB Output is correct
24 Correct 590 ms 354840 KB Output is correct

Subtask #8
0 / 16.0

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