oj.uz

Submission #627389

# Submission time Handle Problem Language Result Execution time Memory
627389 2022-08-12T14:16:55 Z welleyth Catfish Farm (IOI22_fish) C++17
37 / 100
 1000 ms 417084 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
 
constexpr int NN = 1e5 + 10;
constexpr long long INF = (long long)2e18 + 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][3333][3333];
    for(int i = 0; i < 2; i++){
        for(int j = 0; j < 333; j++){
            for(int t = 0; t < 333; 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);
        st[i].insert(N);
        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[1] = 0; pr[1] < possibleLen[i-2].size(); pr[1]++){
            for(int cur = 0; cur < possibleLen[i].size(); cur++){
                int lcur = possibleLen[i][cur];
                int l1 = possibleLen[i-2][pr[1]];
                int p1 = lower_bound(possibleLen[i-1].begin(),possibleLen[i-1].end(),min(l1,lcur)-1) - possibleLen[i-1].begin();
                p1 = min(p1+90,(int)possibleLen[i-1].size()-1);
                for(pr[0] = max(0,p1-80); pr[0] <= p1; pr[0]++){
                    int l0 = possibleLen[i-1][pr[0]];
                    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:49: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]
   49 |         for(int j = 1; j < val[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~
fish.cpp:61:30: 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:34: 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:84:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
      |                        ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:85:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |             for(pr[1] = 0; pr[1] < possibleLen[i-2].size(); pr[1]++){
      |                            ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:89:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
      |                        ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:90:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |             for(int cur = 0; cur < possibleLen[i].size(); cur++){
      |                              ~~~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:94:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for(pr[0] = 0; pr[0] < possibleLen[i-1].size(); pr[0]++){
      |                        ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:95:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |             for(int cur = 0; cur < possibleLen[i].size(); cur++){
      |                              ~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 847 ms 417084 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 178888 KB Output is correct
2 Execution timed out 1099 ms 224612 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 196040 KB Output is correct
2 Correct 107 ms 196012 KB Output is correct
3 Correct 165 ms 200180 KB Output is correct
4 Correct 150 ms 200220 KB Output is correct
5 Correct 213 ms 206192 KB Output is correct
6 Correct 237 ms 206248 KB Output is correct
7 Correct 211 ms 206236 KB Output is correct
8 Correct 205 ms 206388 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 178808 KB Output is correct
2 Correct 71 ms 178796 KB Output is correct
3 Correct 71 ms 178860 KB Output is correct
4 Correct 67 ms 178824 KB Output is correct
5 Correct 67 ms 178840 KB Output is correct
6 Correct 81 ms 178900 KB Output is correct
7 Correct 72 ms 178848 KB Output is correct
8 Correct 69 ms 178888 KB Output is correct
9 Correct 72 ms 178944 KB Output is correct
10 Correct 78 ms 179132 KB Output is correct
11 Correct 78 ms 178928 KB Output is correct
12 Correct 85 ms 179020 KB Output is correct
13 Correct 70 ms 178880 KB Output is correct
14 Correct 73 ms 179020 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 178808 KB Output is correct
2 Correct 71 ms 178796 KB Output is correct
3 Correct 71 ms 178860 KB Output is correct
4 Correct 67 ms 178824 KB Output is correct
5 Correct 67 ms 178840 KB Output is correct
6 Correct 81 ms 178900 KB Output is correct
7 Correct 72 ms 178848 KB Output is correct
8 Correct 69 ms 178888 KB Output is correct
9 Correct 72 ms 178944 KB Output is correct
10 Correct 78 ms 179132 KB Output is correct
11 Correct 78 ms 178928 KB Output is correct
12 Correct 85 ms 179020 KB Output is correct
13 Correct 70 ms 178880 KB Output is correct
14 Correct 73 ms 179020 KB Output is correct
15 Correct 69 ms 178952 KB Output is correct
16 Correct 850 ms 179168 KB Output is correct
17 Execution timed out 1101 ms 183860 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 178808 KB Output is correct
2 Correct 71 ms 178796 KB Output is correct
3 Correct 71 ms 178860 KB Output is correct
4 Correct 67 ms 178824 KB Output is correct
5 Correct 67 ms 178840 KB Output is correct
6 Correct 81 ms 178900 KB Output is correct
7 Correct 72 ms 178848 KB Output is correct
8 Correct 69 ms 178888 KB Output is correct
9 Correct 72 ms 178944 KB Output is correct
10 Correct 78 ms 179132 KB Output is correct
11 Correct 78 ms 178928 KB Output is correct
12 Correct 85 ms 179020 KB Output is correct
13 Correct 70 ms 178880 KB Output is correct
14 Correct 73 ms 179020 KB Output is correct
15 Correct 69 ms 178952 KB Output is correct
16 Correct 850 ms 179168 KB Output is correct
17 Execution timed out 1101 ms 183860 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 196040 KB Output is correct
2 Correct 107 ms 196012 KB Output is correct
3 Correct 165 ms 200180 KB Output is correct
4 Correct 150 ms 200220 KB Output is correct
5 Correct 213 ms 206192 KB Output is correct
6 Correct 237 ms 206248 KB Output is correct
7 Correct 211 ms 206236 KB Output is correct
8 Correct 205 ms 206388 KB Output is correct
9 Correct 430 ms 215680 KB Output is correct
10 Correct 203 ms 196908 KB Output is correct
11 Correct 423 ms 214980 KB Output is correct
12 Correct 74 ms 178832 KB Output is correct
13 Correct 71 ms 178892 KB Output is correct
14 Correct 69 ms 178780 KB Output is correct
15 Correct 69 ms 178864 KB Output is correct
16 Correct 74 ms 178812 KB Output is correct
17 Correct 77 ms 179024 KB Output is correct
18 Correct 105 ms 196088 KB Output is correct
19 Correct 99 ms 196044 KB Output is correct
20 Correct 99 ms 196016 KB Output is correct
21 Correct 97 ms 196108 KB Output is correct
22 Correct 725 ms 215372 KB Output is correct
23 Correct 739 ms 223748 KB Output is correct
24 Correct 704 ms 224724 KB Output is correct

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 847 ms 417084 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -