oj.uz

답안 #1068545

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1068545 2024-08-21T10:32:55 Z Unforgettablepl 메기 농장 (IOI22_fish) C++17
35 / 100
 1000 ms 1802868 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,long long>>> pref(N+2);
    for(int i=0;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;
    }
    auto getpref = [&](int i,int j) {
        auto iter = lower_bound(pref[i].begin(),pref[i].end(),make_pair(j+1,-1ll));
        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 DP[i][j][1]=max(DP[i][j][1],getpref(i,N)-getpref(i,j));
            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 DP[i][j][0]=max(DP[i][j][0],getpref(i-1,N));
            }
            if(i!=2)DP[i][j][0]=max(DP[i][j][0],getpref(i-1,j)+transition4[i-1][j]);
            else DP[i][j][0]=max(DP[i][j][0],getpref(i-1,j));
            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;
}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:24:22: 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]
   24 |         for(int j=1;j<pref[i].size();j++)pref[i][j].second+=pref[i][j-1].second;
      |                     ~^~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1131 ms 1758088 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Execution timed out 1111 ms 1651796 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1132 ms 1802868 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 1 ms 348 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 9 ms 8284 KB Output is correct
11 Correct 3 ms 2392 KB Output is correct
12 Correct 9 ms 8284 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 8 ms 8284 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 1 ms 348 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 9 ms 8284 KB Output is correct
11 Correct 3 ms 2392 KB Output is correct
12 Correct 9 ms 8284 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 8 ms 8284 KB Output is correct
15 Correct 9 ms 8284 KB Output is correct
16 Correct 2 ms 860 KB Output is correct
17 Correct 36 ms 10332 KB Output is correct
18 Correct 27 ms 11356 KB Output is correct
19 Correct 26 ms 11100 KB Output is correct
20 Correct 23 ms 11100 KB Output is correct
21 Correct 24 ms 11100 KB Output is correct
22 Correct 36 ms 13916 KB Output is correct
23 Correct 14 ms 8792 KB Output is correct
24 Correct 25 ms 9724 KB Output is correct
25 Correct 9 ms 8280 KB Output is correct
26 Correct 13 ms 8540 KB Output is correct

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 1 ms 348 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 9 ms 8284 KB Output is correct
11 Correct 3 ms 2392 KB Output is correct
12 Correct 9 ms 8284 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 8 ms 8284 KB Output is correct
15 Correct 9 ms 8284 KB Output is correct
16 Correct 2 ms 860 KB Output is correct
17 Correct 36 ms 10332 KB Output is correct
18 Correct 27 ms 11356 KB Output is correct
19 Correct 26 ms 11100 KB Output is correct
20 Correct 23 ms 11100 KB Output is correct
21 Correct 24 ms 11100 KB Output is correct
22 Correct 36 ms 13916 KB Output is correct
23 Correct 14 ms 8792 KB Output is correct
24 Correct 25 ms 9724 KB Output is correct
25 Correct 9 ms 8280 KB Output is correct
26 Correct 13 ms 8540 KB Output is correct
27 Correct 742 ms 776700 KB Output is correct
28 Correct 172 ms 62032 KB Output is correct
29 Execution timed out 1087 ms 793464 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1132 ms 1802868 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1131 ms 1758088 KB Time limit exceeded
2 Halted 0 ms 0 KB -