oj.uz

Submission #1068509

# Submission time Handle Problem Language Result Execution time Memory
1068509 2024-08-21T10:22:08 Z Unforgettablepl Catfish Farm (IOI22_fish) C++17
52 / 100
 1000 ms 1909328 KB 
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;

long long max_weights(int N, int M,vector<int> X,vector<int> Y,
                      vector<int> W){
    vector DP(N+1,vector(N+1,vector(2,0ll)));
    // vector<vector<pair<int,int>>> pref(N+2);
    // for(int i=1;i<=N+1;i++)pref[i].emplace_back(0,0);
    vector<vector<int>> special_points(N+2);
    for(int i=1;i<=N+1;i++)special_points[i].emplace_back(0);
    for(int i=1;i<=N+1;i++)special_points[i].emplace_back(N);
    vector transition1(N+1,vector(N+1,0ll));
    vector transition2(N+1,vector(N+1,0ll));
    vector transition3(N+1,vector(N+1,0ll));
    vector transition4(N+1,vector(N+1,0ll));
    // for(int i=0;i<M;i++) {
    //     pref[X[i]+1].emplace_back(Y[i]+1,W[i]);
    //     special_points[X[i]+1].emplace_back(Y[i]);
    // }
    // for(int i=1;i<=N+1;i++) {
    //     sort(special_points[i].begin(),special_points[i].end());
    //     sort(pref[i].begin(), pref[i].end());
    //     for(int j=1;j<pref[i].size();j++)pref[i][j].second+=pref[i][j-1].second;
    // }
    vector pref(N+2,vector(N+1,0ll));
    for(int i=0;i<M;i++) {
        pref[X[i]+1][Y[i]+1]=W[i];
    }
    for(int i=1;i<=N;i++)for(int j=1;j<=N;j++)pref[i][j]+=pref[i][j-1];
    auto getpref = [&](int i,int j) {
        return pref[i][j];
        // auto iter = lower_bound(pref[i].begin(),pref[i].end(),make_pair(j+1,-1));
        // iter--;
        // return iter->second;
    };
    for(int i=2;i<=N;i++) {
        for(int j=0;j<=N;j++) {
            if(i!=2)DP[i][j][1]=max(DP[i][j][1],-getpref(i,j)+transition1[i-1][j]);
            else {
                for(int x=j;x<=N;x++) {
                    DP[i][j][1]=max(DP[i][j][1],getpref(i,x)-getpref(i,j)+max(DP[i-1][x][0],DP[i-1][x][1]));
                }
            }
            if(i>2) {
                if(i!=3) {
                    DP[i][j][0]=max(DP[i][j][0],getpref(i-1,j)+transition2[i-2][j]);
                    DP[i][j][0]=max(DP[i][j][0],transition3[i-2][j]);
                }
                else for(int x=0;x<=N;x++) {
                    DP[i][j][0]=max(DP[i][j][0],getpref(i-1,max(x,j))+max(DP[i-2][x][0],DP[i-2][x][1]));
                }
            }
            if(i!=2)DP[i][j][0]=max(DP[i][j][0],getpref(i-1,j)+transition4[i-1][j]);
            else for(int x=0;x<=j;x++) {
                DP[i][j][0]=max(DP[i][j][0],getpref(i-1,j)-getpref(i-1,x)+DP[i-1][x][0]);
            }
            transition1[i][j]=getpref(i+1,j)+max(DP[i][j][0],DP[i][j][1]);
            transition2[i][j]=max(DP[i][j][0],DP[i][j][1]);
            transition3[i][j]=getpref(i+1,j)+max(DP[i][j][0],DP[i][j][1]);
            transition4[i][j]=-getpref(i,j)+DP[i][j][0];
        }
        for(int j=N-1;j>=0;j--)transition1[i][j]=max(transition1[i][j],transition1[i][j+1]);
        for(int j=1;j<=N;j++)transition2[i][j]=max(transition2[i][j],transition2[i][j-1]);
        for(int j=N-1;j>=0;j--)transition3[i][j]=max(transition3[i][j],transition3[i][j+1]);
        for(int j=1;j<=N;j++)transition4[i][j]=max(transition4[i][j],transition4[i][j-1]);
    }
    long long ans = 0;
    for(int j=0;j<=N;j++)ans=max(ans,DP[N][j][0]);
    for(int j=0;j<=N;j++)ans=max(ans,DP[N][j][1]);
    return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Execution timed out 1070 ms 1755480 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 1105 ms 1812072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 10 ms 9088 KB Output is correct
11 Correct 2 ms 2648 KB Output is correct
12 Correct 9 ms 9052 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 9 ms 9052 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 10 ms 9088 KB Output is correct
11 Correct 2 ms 2648 KB Output is correct
12 Correct 9 ms 9052 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 9 ms 9052 KB Output is correct
15 Correct 9 ms 8796 KB Output is correct
16 Correct 1 ms 860 KB Output is correct
17 Correct 16 ms 10840 KB Output is correct
18 Correct 17 ms 10700 KB Output is correct
19 Correct 17 ms 10588 KB Output is correct
20 Correct 17 ms 10588 KB Output is correct
21 Correct 17 ms 10640 KB Output is correct
22 Correct 25 ms 12636 KB Output is correct
23 Correct 11 ms 9304 KB Output is correct
24 Correct 13 ms 10012 KB Output is correct
25 Correct 8 ms 9052 KB Output is correct
26 Correct 9 ms 9352 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 10 ms 9088 KB Output is correct
11 Correct 2 ms 2648 KB Output is correct
12 Correct 9 ms 9052 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 9 ms 9052 KB Output is correct
15 Correct 9 ms 8796 KB Output is correct
16 Correct 1 ms 860 KB Output is correct
17 Correct 16 ms 10840 KB Output is correct
18 Correct 17 ms 10700 KB Output is correct
19 Correct 17 ms 10588 KB Output is correct
20 Correct 17 ms 10588 KB Output is correct
21 Correct 17 ms 10640 KB Output is correct
22 Correct 25 ms 12636 KB Output is correct
23 Correct 11 ms 9304 KB Output is correct
24 Correct 13 ms 10012 KB Output is correct
25 Correct 8 ms 9052 KB Output is correct
26 Correct 9 ms 9352 KB Output is correct
27 Correct 765 ms 847040 KB Output is correct
28 Correct 91 ms 62292 KB Output is correct
29 Correct 801 ms 859728 KB Output is correct
30 Correct 828 ms 859876 KB Output is correct
31 Correct 843 ms 859988 KB Output is correct
32 Correct 128 ms 40936 KB Output is correct
33 Correct 864 ms 859628 KB Output is correct
34 Correct 909 ms 859656 KB Output is correct
35 Correct 797 ms 851836 KB Output is correct
36 Correct 894 ms 859624 KB Output is correct

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1105 ms 1812072 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 1118 ms 1909328 KB Time limit exceeded
2 Halted 0 ms 0 KB -