oj.uz

답안 #661066

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
661066 2022-11-24T07:21:12 Z mychecksedad 메기 농장 (IOI22_fish) C++17
12 / 100
 433 ms 123600 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
const int N = 1e5 + 100;


vector<ll> dp[N][2], pref[N][3], dp_pref[N], dp_suf[N], dp_pref_max[N]; //pref:  0 : itself, 1 : left one, 2 : right one
vector<int> v[N], p[N];

long long max_weights(int n, int m, std::vector<int> x, std::vector<int> y, std::vector<int> w){  

    for(int i = 0; i < m; ++i){
        v[x[i]].pb(i);
        if(x[i] > 0) v[x[i] - 1].pb(i);
        if(x[i] < n - 1) v[x[i] + 1].pb(i);
    }

    for(int i = 0; i <= n; ++i){
        int s = v[i].size() + 1;
        p[i].pb(0);
        for(int a: v[i]) p[i].pb(y[a] + 1);
        sort(p[i].begin(), p[i].end());
        for(int k = 0; k < 3; ++k){
            pref[i][k].resize(s);
        }
        dp[i][0].resize(s);
        dp[i][1].resize(s);
        dp_pref[i].resize(s);
        dp_suf[i].resize(s);
        dp_pref_max[i].resize(s);

        vector<pair<int, int>> all;
        for(int a: v[i]) all.pb({y[a] + 1, a});
        sort(all.begin(), all.end());
        
        for(pair<int, int> &a: all){
            a.first = lower_bound(all.begin(), all.end(), make_pair(a.first, -1)) - all.begin() + 1;
            if(x[a.second] == i) pref[i][0][a.first] = w[a.second];
            else if(x[a.second] == i - 1) pref[i][1][a.first] = w[a.second];
            else pref[i][2][a.first] = w[a.second];
        }   
        for(int k = 0; k < 3; ++k)
            for(int j = 1; j < pref[i][k].size(); ++j) pref[i][k][j] += pref[i][k][j - 1];
    }

    for(int i = 0; i <= n; ++i){
        int s = pref[i][0].size();
        for(int j = 0; j < s; ++j){    
            if(i == 0){
                dp[i][0][j] = dp[i][1][j] = pref[i][2][j];
                continue;
            }

            dp[i][0][j] = pref[i][2][j];

            int pos = upper_bound(p[i - 1].begin(), p[i - 1].end(), p[i][j]) - p[i - 1].begin() - 1;

            if(i == 1){
                dp[i][0][j] += dp_pref[i - 1][pos] + pref[i][1][j];
            }else{  
                int pos2 = upper_bound(p[i - 2].begin(), p[i - 2].end(), p[i][j]) - p[i - 2].begin() - 1;
                dp[i][0][j] += max({dp_pref[i - 1][pos] + pref[i][1][j],
                    dp_suf[i - 2][0],
                    dp_pref_max[i - 2][pos2] + pref[i][1][j] 
                });
            }

            dp[i][1][j] = pref[i][2][j] - pref[i][0][j] + (pos + 1 == dp_suf[i - 1].size() ? 0 : dp_suf[i - 1][pos + 1]);
        }

        for(int j = 0; j < s; ++j){
            if(j == 0){
                dp_pref[i][j] = dp[i][0][j] - pref[i][2][j] - pref[i][0][j];
                dp_pref_max[i][j] = max(dp[i][0][j], dp[i][1][j]) - pref[i][2][j];
            }
            else{
                dp_pref[i][j] = max(dp_pref[i][j - 1], dp[i][0][j] - pref[i][2][j] - pref[i][0][j]);
                dp_pref_max[i][j] = max(dp_pref_max[i][j - 1], max(dp[i][0][j], dp[i][1][j]) - pref[i][2][j]);
            }
        }

        for(int j = s - 1; j >= 0; --j){
            if(j == s - 1){
                dp_suf[i][j] = max(dp[i][0][j], dp[i][1][j]);
            }
            else{
                dp_suf[i][j] = max({dp_suf[i][j + 1], dp[i][0][j], dp[i][1][j]});
            }
        }
    }
    return dp_suf[n][0];
}

Compilation message

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:44:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |             for(int j = 1; j < pref[i][k].size(); ++j) pref[i][k][j] += pref[i][k][j - 1];
      |                            ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:69:68: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             dp[i][1][j] = pref[i][2][j] - pref[i][0][j] + (pos + 1 == dp_suf[i - 1].size() ? 0 : dp_suf[i - 1][pos + 1]);
      |                                                            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 143 ms 62392 KB Output is correct
2 Correct 170 ms 68344 KB Output is correct
3 Correct 71 ms 51928 KB Output is correct
4 Correct 73 ms 52084 KB Output is correct
5 Correct 433 ms 123600 KB Output is correct
6 Correct 402 ms 116300 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Incorrect 235 ms 81724 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '40480577213710'
3 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 51948 KB Output is correct
2 Correct 75 ms 51916 KB Output is correct
3 Correct 121 ms 57840 KB Output is correct
4 Correct 105 ms 57920 KB Output is correct
5 Correct 163 ms 69880 KB Output is correct
6 Correct 159 ms 69904 KB Output is correct
7 Correct 169 ms 69916 KB Output is correct
8 Correct 164 ms 69984 KB Output is correct

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23768 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 13 ms 23740 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 12 ms 23776 KB Output is correct
9 Incorrect 13 ms 23872 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '114136648940'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23768 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 13 ms 23740 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 12 ms 23776 KB Output is correct
9 Incorrect 13 ms 23872 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '114136648940'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23768 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 12 ms 23764 KB Output is correct
6 Correct 13 ms 23740 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Correct 12 ms 23776 KB Output is correct
9 Incorrect 13 ms 23872 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '114136648940'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 51948 KB Output is correct
2 Correct 75 ms 51916 KB Output is correct
3 Correct 121 ms 57840 KB Output is correct
4 Correct 105 ms 57920 KB Output is correct
5 Correct 163 ms 69880 KB Output is correct
6 Correct 159 ms 69904 KB Output is correct
7 Correct 169 ms 69916 KB Output is correct
8 Correct 164 ms 69984 KB Output is correct
9 Correct 161 ms 69984 KB Output is correct
10 Correct 126 ms 56212 KB Output is correct
11 Correct 255 ms 88752 KB Output is correct
12 Correct 12 ms 23764 KB Output is correct
13 Correct 12 ms 23764 KB Output is correct
14 Correct 13 ms 23764 KB Output is correct
15 Correct 11 ms 23764 KB Output is correct
16 Correct 12 ms 23764 KB Output is correct
17 Correct 12 ms 23776 KB Output is correct
18 Correct 74 ms 51964 KB Output is correct
19 Correct 73 ms 51952 KB Output is correct
20 Correct 73 ms 51956 KB Output is correct
21 Correct 76 ms 51964 KB Output is correct
22 Correct 205 ms 67752 KB Output is correct
23 Incorrect 252 ms 88752 KB 1st lines differ - on the 1st token, expected: '77772396150817', found: '81468050166366'
24 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 143 ms 62392 KB Output is correct
2 Correct 170 ms 68344 KB Output is correct
3 Correct 71 ms 51928 KB Output is correct
4 Correct 73 ms 52084 KB Output is correct
5 Correct 433 ms 123600 KB Output is correct
6 Correct 402 ms 116300 KB Output is correct
7 Correct 12 ms 23764 KB Output is correct
8 Incorrect 235 ms 81724 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '40480577213710'
9 Halted 0 ms 0 KB -