oj.uz

Submission #1070828

# Submission time Handle Problem Language Result Execution time Memory
1070828 2024-08-22T19:14:04 Z beaconmc Catfish Farm (IOI22_fish) C++17
44 / 100
 1000 ms 508496 KB 
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "fish.h"
 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
const ll maxn = 100005;
 
 
set<ll> heights[maxn];
vector<ll> realheights[maxn];
 
map<ll,ll> fish[maxn];
map<ll,ll> weights[maxn];
 
map<ll,ll> p[maxn];
 
vector<array<ll,2>>  dp[maxn];
 
map<ll,ll> pref[maxn][2];
map<ll,ll> pref2[maxn][2];
map<ll,ll> suff[maxn][2];
 
 
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
 
    FOR(i,0,M){
        Y[i]++;
        fish[X[i]][Y[i]] = 1;
        weights[X[i]][Y[i]] = W[i];
 
        if (X[i] > 0) heights[X[i]-1].insert(Y[i]);
        if (X[i] > 1) heights[X[i]-2].insert(Y[i]);
        heights[X[i]].insert(Y[i]);
        heights[X[i]+1].insert(Y[i]);
        heights[X[i]+2].insert(Y[i]);
    }
    FOR(i,0,maxn) heights[i].insert(0);
    FOR(i,0,maxn) heights[i].insert(maxn);

 
    FOR(i,0,maxn){
        p[i][0] = 0;
        ll prev = 0;
        for (auto j : heights[i]){
            if (j==0) continue;
            p[i][j] = p[i][prev] + weights[i][j];
            prev = j;
        }
    }
    FOR(i,0,maxn){
        for (auto k : heights[i]) realheights[i].push_back(k);
    }
    FOR(i,0,maxn){
        dp[i].resize(heights[i].size());
    }

 
    FOR(i,1,N+1){

        FOR(X,0,dp[i].size()){
            ll j = realheights[i][X];
            FOR(k,0,2){
 
 
                if (i<2) continue;
                ll temp = 0;
                ll add = 0;
                if (k==0){
                    if (X==dp[i].size()-1) continue;
                    temp = max(temp, suff[i-1][0][j] - p[i-1][j]);
                    temp = max(temp, suff[i-1][1][j] - p[i-1][j]);
 
                    // FOR(p,j+1,N+1){
                    //     if (fish[i-1][p]) add += weights[i-1][p];
                    //     temp = max(temp, dp[i-1][p][0] + add);
                    //     temp = max(temp, dp[i-1][p][1] + add);
                    // }
                }else{
                    temp = max(temp, pref[i-1][0][j]);
                    temp = max(temp, pref[i-1][1][j] + p[i-2][j]);
 
                    // FOR(p,0,j+1) if (fish[i-2][p]) add += weights[i-2][p];
                    // FOR(p,0,j+1){
                    //     if (fish[i-2][p]) add -= weights[i-2][p];
                    //     temp = max(temp, dp[i-1][p][0]);
                    //     temp = max(temp, dp[i-1][p][1] + add);
                    // }
                }
 
 
                dp[i][X][k] = temp;
            }
        }
        ll sz = realheights[i].size();
 
        FOR(k,0,2){
            ll tempadd = 0;
            ll tempadd2 = 0;
 
 
            FOR(j,0,sz){
                tempadd += weights[i][realheights[i][j]];
                suff[i][k][realheights[i][j]] = dp[i][j][k]+tempadd;
            }
 
            FOR(j,0,sz){
                tempadd2 -= weights[i-1][realheights[i][j]];
                pref[i][k][realheights[i][j]] = dp[i][j][k] + tempadd2;
                pref2[i][k][realheights[i][j]] = dp[i][j][k];
            }
            ll prev = 0;
            FOR(j,1,sz){
                pref[i][k][realheights[i][j]] = max(pref[i][k][realheights[i][j]], pref[i][k][prev]);
                pref2[i][k][realheights[i][j]] = max(pref2[i][k][realheights[i][j]], pref2[i][k][prev]);
                prev = realheights[i][j];
            }
            prev = realheights[i][sz-1];
            FORNEG(j,sz-2,-1){
                suff[i][k][realheights[i][j]] = max(suff[i][k][realheights[i][j]], suff[i][k][prev]);
 
                prev = realheights[i][j];
            }
 
        }
        // cout << i << endl;
        // cout << suff[2][2][0] << "FUCK" << endl;
 
    }
 
 
    // cout << dp[3][2][0] << endl;
 
 
 
    ll ans = 0;
 
    FOR(i,0,N+1){
        FOR(j,0,dp[i].size()){
            ans = max(dp[i][j][0], ans);
            ans = max(dp[i][j][1], 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:9:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
   67 |         FOR(X,0,dp[i].size()){
      |             ~~~~~~~~~~~~~~~~     
fish.cpp:67:9: note: in expansion of macro 'FOR'
   67 |         FOR(X,0,dp[i].size()){
      |         ^~~
fish.cpp:76:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |                     if (X==dp[i].size()-1) continue;
      |                         ~^~~~~~~~~~~~~~~~
fish.cpp:74:20: warning: unused variable 'add' [-Wunused-variable]
   74 |                 ll add = 0;
      |                    ^~~
fish.cpp:9:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
  145 |         FOR(j,0,dp[i].size()){
      |             ~~~~~~~~~~~~~~~~     
fish.cpp:145:9: note: in expansion of macro 'FOR'
  145 |         FOR(j,0,dp[i].size()){
      |         ^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1000 ms 276400 KB Output is correct
2 Execution timed out 1051 ms 230340 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 88008 KB Output is correct
2 Execution timed out 1018 ms 237040 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 169300 KB Output is correct
2 Correct 126 ms 169296 KB Output is correct
3 Correct 231 ms 200528 KB Output is correct
4 Correct 216 ms 202352 KB Output is correct
5 Correct 336 ms 235860 KB Output is correct
6 Correct 328 ms 235968 KB Output is correct
7 Correct 326 ms 235940 KB Output is correct
8 Correct 338 ms 235892 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 88092 KB Output is correct
2 Correct 46 ms 87952 KB Output is correct
3 Correct 48 ms 87892 KB Output is correct
4 Correct 46 ms 87980 KB Output is correct
5 Correct 42 ms 87892 KB Output is correct
6 Correct 42 ms 87888 KB Output is correct
7 Correct 46 ms 87888 KB Output is correct
8 Correct 44 ms 87852 KB Output is correct
9 Correct 45 ms 88408 KB Output is correct
10 Correct 46 ms 89684 KB Output is correct
11 Correct 50 ms 88916 KB Output is correct
12 Correct 53 ms 89680 KB Output is correct
13 Correct 47 ms 88328 KB Output is correct
14 Correct 50 ms 89172 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 88092 KB Output is correct
2 Correct 46 ms 87952 KB Output is correct
3 Correct 48 ms 87892 KB Output is correct
4 Correct 46 ms 87980 KB Output is correct
5 Correct 42 ms 87892 KB Output is correct
6 Correct 42 ms 87888 KB Output is correct
7 Correct 46 ms 87888 KB Output is correct
8 Correct 44 ms 87852 KB Output is correct
9 Correct 45 ms 88408 KB Output is correct
10 Correct 46 ms 89684 KB Output is correct
11 Correct 50 ms 88916 KB Output is correct
12 Correct 53 ms 89680 KB Output is correct
13 Correct 47 ms 88328 KB Output is correct
14 Correct 50 ms 89172 KB Output is correct
15 Correct 49 ms 89348 KB Output is correct
16 Correct 48 ms 90312 KB Output is correct
17 Correct 267 ms 132436 KB Output is correct
18 Correct 215 ms 122964 KB Output is correct
19 Correct 242 ms 129960 KB Output is correct
20 Correct 176 ms 119376 KB Output is correct
21 Correct 164 ms 118096 KB Output is correct
22 Correct 377 ms 148052 KB Output is correct
23 Correct 128 ms 112592 KB Output is correct
24 Correct 259 ms 137556 KB Output is correct
25 Correct 53 ms 90452 KB Output is correct
26 Correct 116 ms 106324 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 88092 KB Output is correct
2 Correct 46 ms 87952 KB Output is correct
3 Correct 48 ms 87892 KB Output is correct
4 Correct 46 ms 87980 KB Output is correct
5 Correct 42 ms 87892 KB Output is correct
6 Correct 42 ms 87888 KB Output is correct
7 Correct 46 ms 87888 KB Output is correct
8 Correct 44 ms 87852 KB Output is correct
9 Correct 45 ms 88408 KB Output is correct
10 Correct 46 ms 89684 KB Output is correct
11 Correct 50 ms 88916 KB Output is correct
12 Correct 53 ms 89680 KB Output is correct
13 Correct 47 ms 88328 KB Output is correct
14 Correct 50 ms 89172 KB Output is correct
15 Correct 49 ms 89348 KB Output is correct
16 Correct 48 ms 90312 KB Output is correct
17 Correct 267 ms 132436 KB Output is correct
18 Correct 215 ms 122964 KB Output is correct
19 Correct 242 ms 129960 KB Output is correct
20 Correct 176 ms 119376 KB Output is correct
21 Correct 164 ms 118096 KB Output is correct
22 Correct 377 ms 148052 KB Output is correct
23 Correct 128 ms 112592 KB Output is correct
24 Correct 259 ms 137556 KB Output is correct
25 Correct 53 ms 90452 KB Output is correct
26 Correct 116 ms 106324 KB Output is correct
27 Correct 61 ms 100692 KB Output is correct
28 Execution timed out 1056 ms 267600 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 169300 KB Output is correct
2 Correct 126 ms 169296 KB Output is correct
3 Correct 231 ms 200528 KB Output is correct
4 Correct 216 ms 202352 KB Output is correct
5 Correct 336 ms 235860 KB Output is correct
6 Correct 328 ms 235968 KB Output is correct
7 Correct 326 ms 235940 KB Output is correct
8 Correct 338 ms 235892 KB Output is correct
9 Correct 919 ms 508252 KB Output is correct
10 Correct 297 ms 194336 KB Output is correct
11 Correct 562 ms 300880 KB Output is correct
12 Correct 43 ms 87888 KB Output is correct
13 Correct 42 ms 88088 KB Output is correct
14 Correct 47 ms 87872 KB Output is correct
15 Correct 57 ms 87920 KB Output is correct
16 Correct 46 ms 87900 KB Output is correct
17 Correct 42 ms 87892 KB Output is correct
18 Correct 148 ms 169508 KB Output is correct
19 Correct 143 ms 169256 KB Output is correct
20 Correct 131 ms 169468 KB Output is correct
21 Correct 126 ms 169296 KB Output is correct
22 Correct 953 ms 508496 KB Output is correct
23 Execution timed out 1083 ms 495188 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1000 ms 276400 KB Output is correct
2 Execution timed out 1051 ms 230340 KB Time limit exceeded
3 Halted 0 ms 0 KB -