oj.uz

Submission #1070589

# Submission time Handle Problem Language Result Execution time Memory
1070589 2024-08-22T15:39:54 Z beaconmc Catfish Farm (IOI22_fish) C++17
52 / 100
 1000 ms 728912 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 = 3005;


bool fish[maxn][maxn];
ll weights[maxn][maxn];

ll p[maxn][maxn];



ll dp[maxn][maxn][2];

ll pref[maxn][maxn][2];
ll pref2[maxn][maxn][2];
ll suff[maxn][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,maxn){
        FOR(j,0,maxn){
            weights[i][j] = 0;
            fish[i][j] = false;
            dp[i][j][0] = 0;
            dp[i][j][1] = 0;

            pref[i][j][0] = 0;
            pref[i][j][1] = 0;
            pref2[i][j][0] = 0;
            pref2[i][j][1] = 0;
            suff[i][j][0] = 0;
            suff[i][j][1] = 0;
        }
    }


    FOR(i,0,M){
        Y[i]++;
        fish[X[i]][Y[i]] = true;
        weights[X[i]][Y[i]] = W[i];
    }
    FOR(i,0,maxn){
        p[i][0] = 0;
        FOR(j,1,maxn){
            p[i][j] = p[i][j-1] + weights[i][j];
        }
    }

    FOR(i,0,N+1){
        FOR(j,0,N+1){
            FOR(k,0,2){


                if (i<2) continue;
                ll temp = 0;
                ll add = 0;
                if (k==0){
                    temp = max(temp, suff[i-1][j+1][0] - p[i-1][j]);
                    temp = max(temp, suff[i-1][j+1][1] - 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][j][0]);
                    temp = max(temp, pref[i-1][j][1] + 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][j][k] = temp;
            }
        }

        FOR(k,0,2){
            ll tempadd = 0;
            ll tempadd2 = 0;


            FOR(j,0,N+1){
                tempadd += weights[i][j];
                suff[i][j][k] = dp[i][j][k]+tempadd;
            }

            FOR(j,0,N+1){
                if (i>1) tempadd2 -= weights[i-1][j];
                pref[i][j][k] = dp[i][j][k] + tempadd2;
                pref2[i][j][k] = dp[i][j][k];
            }

            FOR(j,1,N+1){
                pref[i][j][k] = max(pref[i][j][k], pref[i][j-1][k]);
                pref2[i][j][k] = max(pref2[i][j][k], pref2[i][j-1][k]);
            }

            FORNEG(j,N,-1){
                suff[i][j][k] = max(suff[i][j][k], suff[i][j+1][k]);
            }
        }

    }


    ll ans = 0;
    FOR(i,0,N+1) FOR(j,0,N+1)FOR(k,0,2){
        //if (dp[i][j][k]==305) cout << i << " " << j << " " << k << endl;
        ans = max(ans, dp[i][j][k]);
    }
    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:69:20: warning: unused variable 'add' [-Wunused-variable]
   69 |                 ll add = 0;
      |                    ^~~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 715856 KB Output is correct
2 Execution timed out 1121 ms 722204 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 715860 KB Output is correct
2 Correct 232 ms 715948 KB Output is correct
3 Correct 227 ms 715860 KB Output is correct
4 Correct 223 ms 716056 KB Output is correct
5 Correct 215 ms 715856 KB Output is correct
6 Correct 214 ms 715860 KB Output is correct
7 Correct 222 ms 715948 KB Output is correct
8 Correct 223 ms 715980 KB Output is correct
9 Correct 212 ms 716112 KB Output is correct
10 Correct 215 ms 716052 KB Output is correct
11 Correct 219 ms 716000 KB Output is correct
12 Correct 221 ms 715892 KB Output is correct
13 Correct 220 ms 715856 KB Output is correct
14 Correct 216 ms 716116 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 715860 KB Output is correct
2 Correct 232 ms 715948 KB Output is correct
3 Correct 227 ms 715860 KB Output is correct
4 Correct 223 ms 716056 KB Output is correct
5 Correct 215 ms 715856 KB Output is correct
6 Correct 214 ms 715860 KB Output is correct
7 Correct 222 ms 715948 KB Output is correct
8 Correct 223 ms 715980 KB Output is correct
9 Correct 212 ms 716112 KB Output is correct
10 Correct 215 ms 716052 KB Output is correct
11 Correct 219 ms 716000 KB Output is correct
12 Correct 221 ms 715892 KB Output is correct
13 Correct 220 ms 715856 KB Output is correct
14 Correct 216 ms 716116 KB Output is correct
15 Correct 228 ms 716112 KB Output is correct
16 Correct 213 ms 716080 KB Output is correct
17 Correct 229 ms 717448 KB Output is correct
18 Correct 234 ms 717560 KB Output is correct
19 Correct 234 ms 717452 KB Output is correct
20 Correct 245 ms 717648 KB Output is correct
21 Correct 233 ms 717524 KB Output is correct
22 Correct 239 ms 719088 KB Output is correct
23 Correct 242 ms 716408 KB Output is correct
24 Correct 229 ms 717296 KB Output is correct
25 Correct 229 ms 715908 KB Output is correct
26 Correct 235 ms 716360 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 715860 KB Output is correct
2 Correct 232 ms 715948 KB Output is correct
3 Correct 227 ms 715860 KB Output is correct
4 Correct 223 ms 716056 KB Output is correct
5 Correct 215 ms 715856 KB Output is correct
6 Correct 214 ms 715860 KB Output is correct
7 Correct 222 ms 715948 KB Output is correct
8 Correct 223 ms 715980 KB Output is correct
9 Correct 212 ms 716112 KB Output is correct
10 Correct 215 ms 716052 KB Output is correct
11 Correct 219 ms 716000 KB Output is correct
12 Correct 221 ms 715892 KB Output is correct
13 Correct 220 ms 715856 KB Output is correct
14 Correct 216 ms 716116 KB Output is correct
15 Correct 228 ms 716112 KB Output is correct
16 Correct 213 ms 716080 KB Output is correct
17 Correct 229 ms 717448 KB Output is correct
18 Correct 234 ms 717560 KB Output is correct
19 Correct 234 ms 717452 KB Output is correct
20 Correct 245 ms 717648 KB Output is correct
21 Correct 233 ms 717524 KB Output is correct
22 Correct 239 ms 719088 KB Output is correct
23 Correct 242 ms 716408 KB Output is correct
24 Correct 229 ms 717296 KB Output is correct
25 Correct 229 ms 715908 KB Output is correct
26 Correct 235 ms 716360 KB Output is correct
27 Correct 330 ms 716008 KB Output is correct
28 Correct 298 ms 724868 KB Output is correct
29 Correct 388 ms 728660 KB Output is correct
30 Correct 418 ms 728660 KB Output is correct
31 Correct 376 ms 728544 KB Output is correct
32 Correct 272 ms 728408 KB Output is correct
33 Correct 380 ms 728912 KB Output is correct
34 Correct 381 ms 728660 KB Output is correct
35 Correct 390 ms 720724 KB Output is correct
36 Correct 369 ms 728752 KB Output is correct

Subtask #7
0 / 14.0

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

Subtask #8
0 / 16.0

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