oj.uz

Submission #1070586

# Submission time Handle Problem Language Result Execution time Memory
1070586 2024-08-22T15:38:51 Z beaconmc Catfish Farm (IOI22_fish) C++17
35 / 100
 110 ms 23096 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 = 305;


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 Runtime error 80 ms 19312 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 3 ms 7768 KB Output is correct
2 Runtime error 110 ms 23096 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7772 KB Output is correct
2 Correct 5 ms 7780 KB Output is correct
3 Correct 3 ms 7772 KB Output is correct
4 Correct 4 ms 7772 KB Output is correct
5 Correct 4 ms 7772 KB Output is correct
6 Correct 3 ms 7768 KB Output is correct
7 Correct 3 ms 7772 KB Output is correct
8 Correct 4 ms 7820 KB Output is correct
9 Correct 3 ms 7832 KB Output is correct
10 Correct 5 ms 7840 KB Output is correct
11 Correct 4 ms 7772 KB Output is correct
12 Correct 5 ms 7624 KB Output is correct
13 Correct 4 ms 7600 KB Output is correct
14 Correct 5 ms 7772 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7772 KB Output is correct
2 Correct 5 ms 7780 KB Output is correct
3 Correct 3 ms 7772 KB Output is correct
4 Correct 4 ms 7772 KB Output is correct
5 Correct 4 ms 7772 KB Output is correct
6 Correct 3 ms 7768 KB Output is correct
7 Correct 3 ms 7772 KB Output is correct
8 Correct 4 ms 7820 KB Output is correct
9 Correct 3 ms 7832 KB Output is correct
10 Correct 5 ms 7840 KB Output is correct
11 Correct 4 ms 7772 KB Output is correct
12 Correct 5 ms 7624 KB Output is correct
13 Correct 4 ms 7600 KB Output is correct
14 Correct 5 ms 7772 KB Output is correct
15 Correct 5 ms 7772 KB Output is correct
16 Correct 4 ms 7760 KB Output is correct
17 Correct 16 ms 9620 KB Output is correct
18 Correct 12 ms 9564 KB Output is correct
19 Correct 14 ms 9632 KB Output is correct
20 Correct 12 ms 9564 KB Output is correct
21 Correct 14 ms 9564 KB Output is correct
22 Correct 28 ms 11220 KB Output is correct
23 Correct 7 ms 7920 KB Output is correct
24 Correct 10 ms 8840 KB Output is correct
25 Correct 4 ms 7772 KB Output is correct
26 Correct 7 ms 8284 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7772 KB Output is correct
2 Correct 5 ms 7780 KB Output is correct
3 Correct 3 ms 7772 KB Output is correct
4 Correct 4 ms 7772 KB Output is correct
5 Correct 4 ms 7772 KB Output is correct
6 Correct 3 ms 7768 KB Output is correct
7 Correct 3 ms 7772 KB Output is correct
8 Correct 4 ms 7820 KB Output is correct
9 Correct 3 ms 7832 KB Output is correct
10 Correct 5 ms 7840 KB Output is correct
11 Correct 4 ms 7772 KB Output is correct
12 Correct 5 ms 7624 KB Output is correct
13 Correct 4 ms 7600 KB Output is correct
14 Correct 5 ms 7772 KB Output is correct
15 Correct 5 ms 7772 KB Output is correct
16 Correct 4 ms 7760 KB Output is correct
17 Correct 16 ms 9620 KB Output is correct
18 Correct 12 ms 9564 KB Output is correct
19 Correct 14 ms 9632 KB Output is correct
20 Correct 12 ms 9564 KB Output is correct
21 Correct 14 ms 9564 KB Output is correct
22 Correct 28 ms 11220 KB Output is correct
23 Correct 7 ms 7920 KB Output is correct
24 Correct 10 ms 8840 KB Output is correct
25 Correct 4 ms 7772 KB Output is correct
26 Correct 7 ms 8284 KB Output is correct
27 Runtime error 8 ms 14036 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

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

Subtask #8
0 / 16.0

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